順列(Permutation)を発生するアルゴリズムを用いた文字列並べ替えコード。

与えられた文字列の順番を入れ替えて、全てを表示します。
同じダブった文字を含む文字列は、ダブったままの処理をします。
n!個の文字列が出力されます。

C

アルゴリズムは、技術評論社の、「C言語による最新アルゴリズム辞典」（奥村晴彦著）を参考にしました。
ターミナルのCの開発環境があれば、簡単にコンパイルできます。

to compile: cc kuu.c -o kuu
Usage: kuu word

kuu.c

#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>
#define TRUE    1
#define FALSE   0
int     N;
int     p[256];
int     count;
int     ok[257];
char    word[256];

void    show(void) {
    int i;

    count++; printf("%12d: ",count);
    for(i=0;i<N;i++) {
        printf("%c",word[p[i]-1]);
        }
    printf("\n");
}

void    put(int pos,int k) {
    int j;
    p[pos]=k;
    if (pos==N-1) show();
    else {
        ok[k]=FALSE;
        for(j=1;j<=N;j++)
            if(ok[j]) put(pos+1,j);
        ok[k]=TRUE;
        }
}

void genperm1(void)
{
    int k;

    count=0;
    for(k=1;k<=N;k++) ok[k]=TRUE;
    for(k=1;k<=N;k++) put(0,k);

}

int main(int argc,char *argv[])
{
    if (argc!=2) {
        fprintf(stderr,"Usage kuu word\n");
        exit(1);
        }
    sscanf(argv[1],"%s",word);
    N=strlen(word);
    genperm1();
}

python

itertoolsのpermutationsを使って書いたらこうなります。ずいぶん、スッキリしますね。

kuu.py

#!/usr/bin/python3
import sys
import itertools

word = sys.argv[1]
i=1
for p in itertools.permutations(word, len(word)):
    print("%8d" % i, ':', ''.join(p))
    i+=1

実行結果

$ kuu alice
           1: alice
           2: aliec
           3: alcie
           4: alcei
           5: aleic
           6: aleci
           7: ailce
           8: ailec
           9: aicle
          10: aicel
          11: aielc
          12: aiecl
          13: aclie
          14: aclei
          15: acile
          16: aciel
          17: aceli
          18: aceil
          19: aelic
          20: aelci
          21: aeilc
          22: aeicl
          23: aecli
          24: aecil
          25: laice
          26: laiec
          27: lacie
          28: lacei
          29: laeic
          30: laeci
          31: liace
          32: liaec
          33: licae
          34: licea
          35: lieac
          36: lieca
          37: lcaie
          38: lcaei
          39: lciae
          40: lciea
          41: lceai
          42: lceia
          43: leaic
          44: leaci
          45: leiac
          46: leica
          47: lecai
          48: lecia
          49: ialce
          50: ialec
          51: iacle
          52: iacel
          53: iaelc
          54: iaecl
          55: ilace
          56: ilaec
          57: ilcae
          58: ilcea
          59: ileac
          60: ileca
          61: icale
          62: icael
          63: iclae
          64: iclea
          65: iceal
          66: icela
          67: iealc
          68: ieacl
          69: ielac
          70: ielca
          71: iecal
          72: iecla
          73: calie
          74: calei
          75: caile
          76: caiel
          77: caeli
          78: caeil
          79: claie
          80: claei
          81: cliae
          82: cliea
          83: cleai
          84: cleia
          85: ciale
          86: ciael
          87: cilae
          88: cilea
          89: cieal
          90: ciela
          91: ceali
          92: ceail
          93: celai
          94: celia
          95: ceial
          96: ceila
          97: ealic
          98: ealci
          99: eailc
         100: eaicl
         101: eacli
         102: eacil
         103: elaic
         104: elaci
         105: eliac
         106: elica
         107: elcai
         108: elcia
         109: eialc
         110: eiacl
         111: eilac
         112: eilca
         113: eical
         114: eicla
         115: ecali
         116: ecail
         117: eclai
         118: eclia
         119: ecial
         120: ecila

同じ文字を含む文字列の出力例

$ kuu kuu
           1: kuu
           2: kuu
           3: uku
           4: uuk
           5: uku
           6: uuk