配列のすべての並べ替え方を列挙するプログラム

任意の要素の配列(重複あり)について、その並べ方が何通りあるかを求めるプログラムは割と簡単に書けます。(重複が無い場合は_nP_mを求めればよい。)

今回は力試しの意味も込めて、すべての並べ方を列挙するプログラムをDで書いてみました。

module p;
import std.cstream;

T[][] get_permutation(T)(T[] array) {
    if(array.length <= 1)
        return [array];
    T[][] result;
    result.length = 10;
    int idx = 0;
    int[] except_idx = [];
    loop:
    for(int i=0; i<array.length; i++) {
        for(int j=i+1; j<array.length; j++)
            if(array[i] == array[j])
                except_idx ~= j;
        foreach(eidx; except_idx)
            if(i == eidx)
                continue loop;
        T[][] temp = get_permutation(array[0..i] ~ array[i+1..$]);
        for(int j=0; j<temp.length; j++) {
            if(idx == result.length)
                result.length = result.length * 2;
            result[idx] = array[i] ~ temp[j];
            idx++;
        }
    }
    result.length = idx;
    return result;
}

void main() {
    auto array = get_permutation(cast(char[])"array");
    dout.writefln(array.length, \n, array.sort);
}

結果

30
[aarry,aaryr,aayrr,arary,arayr,array,arrya,aryar,aryra,ayarr,ayrar,ayrra,raary,r
aayr,raray,rarya,rayar,rayra,rraay,rraya,rryaa,ryaar,ryara,ryraa,yaarr,yarar,yar
ra,yraar,yrara,yrraa]

arrayは重複する文字が2文字ずつ2組あるので、並べ替え方は
通りとなります。
どうやら正しく動作しているようですね。