配列組合せアルゴリズムまとめ(C++ベース)

1.配列
全配列n!
1.1再帰法
一組の数p={r 1,r 2,r 3,...,rn}をperm(p),pn=p−{rn}とする.perm(p)=r 1 perm(p 1),r 2 perm(p 2),r 3 perm(p 3),...,rnperm(pn)である.n=1のときperm(p}=r 1.
例えば:{1,2,3,4,5}の全配列を求める
1、まず最後の2つの数4、5を見ます.これらの全配列は4 5と5 4、すなわち4で始まる5の全配列と5で始まる4の全配列である.
1つの数の全配列がそれ自体であるため,以上の結果が得られる.
2、後ろの3つを見て3、4、5を数えます.これらの全配列は、3 4 5、3 5 4、4 3 5、4 5 3、5 3 4、5 4 3の6群数である.
すなわち、3で始まる和4,5の全配列の組み合わせ、4で始まる和3,5の全配列の組み合わせ、5で始まる和3,4の全配列の組み合わせである.

#include 
using namespace std;

void Perm(int start, int end, int a[]) {
    //          ，    
    if (start == end) {
        for (int i = 0; i < end; i++)
            cout << a[i] << ' ';
        cout << endl;
        return;
    }
    for (int i = start; i < end; i++) {
        swap(a[start], a[i]);      //  
        Perm(start + 1, end, a);   //      a[start+1,...,end-1]    
        swap(a[i], a[start]);      //  
    }
}
int main() {
    int i, n, a[10];
    while (cin >> n, n) {
        for (i = 0; i < n; i++)
        {
            a[i] = i + 1;
        }
        Perm(0, n, a);
    }
    return 0;
}

2.組み合わせ
C(n,k),n個の数のうち任意にk個の数をとる
2.1再帰法
実際にはn個の数にk個の数をマークし、このk個の数を出力するプロセスである.visited配列を使用して、対応する下付きスケールの数が選択されているかどうかを記録します.

#include 
using namespace std;

void dfs(int pos, int cnt, int n, int k, int a[],bool visited[]) {
    //    k  ，    
    if (cnt == k) {
        for (int i = 0; i < n; i++)
            if (visited[i]) cout << a[i] << ' ';
        cout << endl;
        return;
    }

    //        ，    
    if (pos == n) return;

    //  a[pos]     
    if (!visited[pos]) {
        //  a[pos]
        visited[pos] = true;
        //     a[pos+1, n-1]   k-1      
        dfs(pos + 1, cnt + 1, n, k, a,visited);
        //  
        visited[pos] = false;   
    }
    //     a[pos+1, n-1]   k     
    dfs(pos + 1, cnt, n, k, a, visited);
}
int main() {
    int i, n, k;
    while (cin >> n >> k, n || k) 
    {
        int *a = new int[n];
        bool *visited = new bool[n];
        for (i = 0; i < n; i++)
        {
            a[i] = i + 1;
            visited[i] = false;
        }
        dfs(0, 0, n, k, a, visited);
        delete[] a;
        delete[] visited;
    }
    getchar();
    return 0;
}

2.2‘01’変換法
本プログラムの構想は1つの配列を開いて、その下の標識は1からnの数を表して、配列の要素の値は1でその代表の数が選択されたことを表して、0で選択されていません.
まず初期化し,配列の前のn個の要素を1にし,最初の組合せが前のn個の数であることを示す.
次に、配列要素値の「10」の組合せを左から右にスキャンし、最初の「10」の組合せを見つけて「01」の組合せにし、左側のすべての「1」を配列の左端に移動します.
最初の「1」が配列のn−mの位置,すなわちn個の「1」がすべて最右端に移動すると,最後の組合せが得られる.
例えば5の中で3の組み合わせを選ぶことを求めます:
1 1 1 0 0//1,2,3
1 1 0 1 0//1,2,4
1 0 1 1 0//1,3,4
0 1 1 1 0//2,3,4
1 1 0 0 1//1,2,5
1 0 1 0 1//1,3,5
0 1 1 0 1//2,3,5
1 0 0 1 1//1,4,5
0 1 0 1 1//2,4,5
0 0 1 1 1//3,4,5

#include 

using namespace std;

//    
void printRes(int* a, bool* index, int n)
{
    for (int i=0;iif (index[i])
        {
            cout << a[i] << " ";
        }
    }
    cout << endl;
}

//    k         0
bool hasDone(bool* index, int n, int k)
{
    for (int i=n-1;i>=n-k;i--)
    {
        if (!index[i])
        {
            return false;
        }
    }
    return true;
}

void Comb(int* a, int n, int k)
{
    bool *index = new bool[n]();
    //   k   
    for (int i = 0; i < k; i++)
    {
        index[i] = true;
    }
    printRes(a, index, n);

    while (!hasDone(index, n, k))
    {
        //        
        for (int i = 0; i < n - 1; i++)
        {
            //     “10”      "01"  
            if (index[i] && !index[i + 1])
            {
                index[i] = false;
                index[i + 1] = true;

                // "01"     1     
                int count = 0;
                for (int j = 0; j < i; j++)
                {
                    if (index[j])
                    {
                        index[j] = false;
                        index[count++] = true;
                    }
                }
                printRes(a, index, n);
                break;
            }
        }
    }
    delete[] index;
}
int main()
{
    int n,k;
    while (cin>>n>>k)
    {
        int *a = new int[n]();
        for (int i = 0; i < n; i++)
        {
            a[i] = i+1;
        }
        Comb(a, n, k);
        delete[] a;
    }

    return 0;
}