順列生成アルゴリズム

Full BASICはリスト処理が苦手です。文字列処理でリスト処理を代替します。
次の外部副プログラムは，s$に続けてt$に含まれる文字の順列を出力します。

200 EXTERNAL SUB Permutate(s$,t$)
210 IF t$="" THEN
220    PRINT s$
230 ELSE 
240    FOR i=1 TO LEN(t$)
250       LET x$=s$ & t$(i:i)
260       LET y$=t$(1:i-1) & t$(i+1:LEN(t$)) 
270       CALL Permutate(x$,y$)
280    NEXT i
290 END IF
300 END SUB

たとえば，CALL Permutate("12", "345") を実行すると

12345
12354
12435
12453
12534
12543

を出力します。
t$が空文字列であれば，s$自体が出力すべき順列です(210, 220行)。
t$が空でなければ，250行と260行でs$にt$から1文字取って繋げてx$とし，t$からその1文字を抜いたリストをy$として，Permutate(x$,y$)を呼び出します(250〜270行)。
この処理をt$の各文字に対し適用します(240〜280行)。

実際に順列を生成するときは，第1引数に空文字列，第2引数に順列を生成したい文字の集合をセットして外部副プログラムPermutateを呼び出します。
例

100 DECLARE EXTERNAL SUB Permutate
110 CALL Permutate("", "12345")
120 END
200 EXTERNAL SUB Permutate(s$,t$)
210 IF t$="" THEN
220    PRINT s$
230 ELSE 
240    FOR i=1 TO LEN(t$)
250       LET x$=s$ & t$(i:i)
260       LET y$=t$(1:i-1) & t$(i+1:LEN(t$)) 
270       CALL Permutate(x$,y$)
280    NEXT i
290 END IF
300 END SUB

全順列を配列に取得する

順列のリストを得たいときは，配列を渡してその配列に得られた順列を追加します。

100 DECLARE EXTERNAL SUB perm
110 LET s$="123"
120 DIM p$(FACT(LEN(s$)))
130 LET k=0
140 CALL perm("", "123",p$,k)
150 FOR i=1 TO k
160    PRINT p$(i)
170 NEXT i
180 END
200 EXTERNAL SUB perm(s$,t$,p$(),k)
210 IF t$="" THEN
215    LET k=k+1
220    LET p$(k)=s$
230 ELSE 
240    FOR i=1 TO LEN(t$)
250       LET x$=s$ & t$(i:i)
260       LET y$=t$(1:i-1) & t$(i+1:LEN(t$)) 
270       CALL perm(x$,y$,p$,k)
280    NEXT i
290 END IF
300 END SUB

160行の部分で各順列に対応した処理を実行します。

戻る