perlの再帰プログラミング

Yahoo知恵袋の質問。

すべての組み合わせを求めるプログラムを作成したいです

アルファベット順に従いAから任意の文字数抽出し、それらを並び替えたときのすべての組み合わせを表示するプログラムを作成したいとおもっています。

例えばABCと入力したらそれを並び替えたときのすべての組み合わせ
ABC
ACB
BAC
BCA
CAB
CBA
の6パターン(3!)表示され
ABCDと入力したらそれを並び替えたときのすべての組み合わせ
ABCD
ABDC
ACBD
ACDB
…
といった具合に24 パターン(4!)が表示される

このようなプログラムです。

perlを使って作成しようと試みています。
具体的なコードというよりは、どのようなアルゴリズムで構築すればよいか
アドバイスをいただけるとうれしいです。

（ここまで）

それに対する私の回答

例えば A B C D の4要素があったとする。これは、次の4種類に分類できる。

(1) Aと、それ以外（すなわちBCD）
(2) Bと、それ以外（すなわちACD）
(3) Cと、それ以外（すなわちABD）
(4) Dと、それ以外（すなわちABC）

ここで、(1)を掘り下げると、次の3種類に分類できる。

(1.1) Aと、Bと、それ以外（すなわちCD）
(1.2) Aと、Cと、それ以外（すなわちBD）
(1.3) Aと、Dと、それ以外（すなわちBC）

さらに、(1.1)を掘り下げると、次の2種類に分類できる。

(1.1.1) Aと、Bと、Cと、それ以外（すなわちD）
(1.1.2) Aと、Bと、Dと、それ以外（すなわちC）

この調子で(4.3.2)まで行うと、結果的に、求める全ての組み合わせができる。

与えられた要素のうちの1つを切り出し、それ以外と分ける。これを与えられた要素分だけ繰り返す。
そして、「それ以外」のうちの1つを切り出し、『それ以外』と分ける。これを「それ以外」のだけ繰り返す。
そして、『それ以外』のうちの1つを切り出し…
…このプロセスを、【それ以外】がたった1つになってしまうまで繰り返す。たった1つになってしまったら、これまで積み上げてきた「1つを切り出し」たものと、たった1つの【それ以外】を並べて表示する。

これを実現するのは、再帰呼び出しを使うのが適しています。

（ここまで）

面白いので、実際に作ってみた。

#!/usr/bin/perl
use strict;

# 処理の都合上、ダミー値を第0要素に挿入してから処理実行
unshift (@ARGV, '');
getCombination (@ARGV);

##########################
# 組み合わせを求める処理
##########################
sub getCombination{
    # 要素数が2まで減ったら、これ以上探索できないので
    if ($#_ == 1){
        # 引き継ぎ分も含め、単純に表示して抜ける
        print "@_\n";
        return;
    }

    # 第0要素は、前段から引き継いだ値なので待避
    my $PrevBaton = shift (@_);

    # 今回処理したい要素分だけループ
    foreach my $NextBaton (@_){

        # 次段に託したい配列を作成
        my @NextArg;
        foreach my $tmp (@_){
            # 新たに次段へ引き継ぐ値を除いて作成する
            $tmp eq $NextBaton or push (@NextArg, $tmp);
        }

        # 「前段から引き継いだ値＋今回の引き継ぎ値」を第0要素として
        unshift (@NextArg, "$PrevBaton $NextBaton");

        # 次段に託す
        getCombination (@NextArg);
    }
}

実行結果イメージは以下のとおり。

$ ./recursive.pl A B C D
 A B C D
 A B D C
 A C B D
 A C D B
 A D B C
 A D C B
 B A C D
 B A D C
 B C A D
 B C D A
 B D A C
 B D C A
 C A B D
 C A D B
 C B A D
 C B D A
 C D A B
 C D B A
 D A B C
 D A C B
 D B A C
 D B C A
 D C A B
 D C B A