読者です 読者をやめる 読者になる 読者になる

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

D言語 数学

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

今回は力試しの意味も込めて、すべての並べ方を列挙するプログラムを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組あるので、並べ替え方は
\frac{5!}{2!2!}=\frac{120}{4}=30通りとなります。
どうやら正しく動作しているようですね。