C++で配列のk個の異なる順列（インデックス）を出力するプログラム

N個の整数を含む配列 a[] が与えられたとき、そのインデックスのk個の異なる順列を出力することを考えます。ただし、それぞれの順列において、そのインデックスに対応する値が非減少列（昇順または同じ値が並ぶ列）になる必要があります。条件を満たす順列がk個作れない場合は -1 を出力します。

入出力例

入力: arr[] = {2,5,6,2,2,2,2}, k = 4
出力:
    0 3 4 5 6 1 2
    3 0 4 5 6 1 2
    0 3 4 5 6 1 2
    3 0 4 5 6 1 2

解法のアプローチ

まず与えられた配列をソートし、同時に各要素の元のインデックスを記録しておきます。これにより、1つ目の条件を満たす順列が得られます。

次に、ソート後の配列で隣り合う2つの要素の値が等しい場合、それらの位置を入れ替えることで別の有効な順列を生成できます。この操作を繰り返すことで、2つ目、3つ目と順列を作っていきます。

アルゴリズム

START
Step 1 -> 関数 void indice(int n, pair<int, int> array[]) を宣言
    int i=0 から i<n までループ
        array[i].second を出力
    ループ終了
Step 2 -> 関数 void permutation(int n, int a[], int k) を宣言
    STL の pair<int, int> arr[n] を使用
    int i=0 から i<n までループ
        arr[i].first = a[i] を設定
        arr[i].second = i を設定
    ループ終了
    sort(arr, arr + n) を呼び出す
    int count を 1 で初期化
    int i=1 から i<n までループ
        IF (arr[i].first == arr[i - 1].first)
            count を 1 増やす
        End
    ループ終了
    IF count < k
        -1 を返す
    End
    int i = 0 から i < k - 1 までループ
        indice(n, arr) を呼び出す
        int j = 1 から j < n までループ
            IF arr[j].first == arr[j - 1].first
                swap(arr[j], arr[j - 1]) を呼び出す
                Break
            End
        ループ終了
    ループ終了
    indice(n, arr) を呼び出す
Step 3 -> main() 内で
    配列 a[]={2,5,6,2,2,2,2} を宣言
    int n = sizeof(a)/sizeof(a[0]) を宣言
    int k = 4 を宣言
    permutation(n, a, k) を呼び出す
STOP

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void indice(int n, pair<int, int> array[]){
    for (int i = 0; i < n; i++)
        cout << array[i].second << " ";
    cout << endl;
}
void permutation(int n, int a[], int k){
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++){
        arr[i].first = a[i];
        arr[i].second = i;
    }
    sort(arr, arr + n);
    int count = 1;
    for (int i = 1; i < n; i++)
        if (arr[i].first == arr[i - 1].first)
            count++;
    if (count < k){
        cout << "-1";
        return;
    }
    for (int i = 0; i < k - 1; i++){
        indice(n, arr);
        for (int j = 1; j < n; j++){
            if (arr[j].first == arr[j - 1].first){
                swap(arr[j], arr[j - 1]);
                break;
            }
        }
    }
    indice(n, arr);
}
int main(){
    int a[] ={2,5,6,2,2,2,2};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 4;
    permutation(n, a, k);
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

0 3 4 5 6 1 2
3 0 4 5 6 1 2
0 3 4 5 6 1 2
3 0 4 5 6 1 2

この結果からわかるように、重複した値（この例では「2」）を持つ要素のインデックスを隣接箇所で入れ替えることで、値の非減少性を保ちながら複数の異なる順列を効率的に生成できています。