順列の内容をすべて表示するプログラムについて

例えば、１，２，３というのは3つの数字であり、順列の数は３！=6となり、
123
132
213
231
312
321
となります（重複なしのシャッフルだけということです）。数字を全部使うと、0123456789の10個であり個数は10！です。（自然数という意味だったら先頭が0だとダメとかありますがそれは考えないとして）。またアルファベット26文字を並び替えると26！通りになります。それを全部表示するアルゴリズムはどのようなものがあるでしょうか。ちょっと考えてみましたが、思いつきません。
pythonだと1000！とか10000!の数を表示してくれます。しかし例えば１1だと0～１0までの数字を並び変えるので二けただと変則的かなと思いますが。とにかく、N!個の順列を全部表示してくれるアルゴリズムはどうなるでしょうか。

できれば言語の仕様に特化したものでない方がいいのですが。あるいはそのような機能がライブラリに含まれているような言語でない方がいいです。

よろしくお願いします。

No.11 回答者： galapagos299800 回答日時： 2018/10/05 09:56

正方行列のデターミネントを定義通りに計算する時に用いる関数で、ｎ個の数値をすべての順列をある順番に並べた場合、ｋ番目（ｋ　＜＝　ｎ！）の順列を返すものがありましたが、今、行方不明です。

この関数は、順列の符号（偶置換？奇置換？）も返してくれるので、デターミネントを計算する時に浮動小数点を使う必要がなくなるので便利ですので、探しておきます。これを読めば、知っている人がいると思うので、期待できるでしょう。
内部のロジックとしては、何種類かあるみたいで、高速のものが見つかれば幸いです。

No.10 回答者： tknakamuri 回答日時： 2018/10/03 01:39

やっぱり再帰が楽ですね。

今度は切り張りで作るバージョン

No.9 回答者： Tacosan 回答日時： 2018/10/03 01:38

たとえば C++ では「次の順列を求める」関数 std::next_permutation があるので, これの実装を流用すれば

再帰を使わないで全ての順列を列挙する
ことは可能です.

No.8 回答者： cametan_42 回答日時： 2018/10/03 00:28

> できれば言語の仕様に特化したものでない方がいいのですが。

あるいはそのような機能がライブラリに含まれているような言語でない方がいいです。

これは利用するプログラミング言語に例えばマッピングに類する機能が無いと非常に面倒くさい問題ですよ。
そもそも、このテの問題は元々、PrologとかLisp向きの問題であってCには向いていない。
Pythonは結構「丁度良い」ですが、それは現代的で内包表記を持ってるから、です。
Cでは解けなくはないだろうけど、恐らくC++のSTLを利用した方が「解きやすい」。C#ならもっとラクかも。
そういう性質の問題です。

def perm(lst):
　　def loop(lst, remain):
　　　　if remain == []:
　　　　　　return []
　　　　elif lst[1:] == []:
　　　　　　return [lst]
　　　　else:
　　　　　　return [[lst[0]] + l for l in perm(lst[1:])]\
　　　　　　　　　　+\
　　　　　　　　　　loop(lst[1:] + [lst[0]], remain[1:])
　　return loop(lst, lst)

No.7 回答者： tatsu99 回答日時： 2018/10/02 23:24

A,B,C,Dの順列のケースです。

python3です。
再帰呼び出しをする方法
https://ideone.com/2ClmMo

再帰呼び出しをしない方法
https://ideone.com/kyq6kM

上記URLを参照ください。
尚、再帰呼び出しをする方法の場合は
arr = ["A","B","C","D"]の箇所を
arr = ["A","B","C","D","E"]
のようにすれば、A,B,C,D,Eの順列が求められます。

arr = ["A","B","C","D","E"・・・途中省略・・・,"Z"]
とすれば、アルファベット２６文字も可能です。（完了までに莫大な時間がかかると思いますが・・・）

No.6 回答者： tatsu99 回答日時： 2018/10/02 19:55

よこから失礼します。

No5の方へ
よろしければ、そのソースをこちらに張り付けていただけませんでしょうか。
こちらは、インデントが乱れませんので、そのままのソースが保たれます。
https://ideone.com/

１．添付図の左側の赤線で囲んだところで、言語を選択してください。
２．次に青線で囲んだところにソースを張り付けてください。（your code goes hereの文字を削除してからです）
３．Run（右側の赤線で囲んだところ）をクリックしてください。
４．実行結果表示され、ソースが登録されるので、そのURLをこのサイトに投稿してください。

そうすると、質問者の方も、そのソースをコピペできるので、確認がしやくすなるかと。

No.5 回答者： tknakamuri 回答日時： 2018/10/02 19:11

もう少し綺麗なイメージ

No.4 回答者： tknakamuri 回答日時： 2018/10/02 17:56

非再帰だととっても面倒くさいんですよね。

No.3 回答者： tknakamuri 回答日時： 2018/10/02 14:36

AN02です。

いけね、Cのカテですね。pythonで書いてます(^-^;
変換するのは容易なので、御参考まで。

この回答へのお礼

回答ありがとうございます。pythonで結構です。動作確認しました。
ところで１つ教えて頂きたいのですが、このプログラムは関数再帰呼び出しということによって実現すると理解してよいでしょうか。私は関数再帰呼び出しができない言語ばかりで仕事をしてきたのでコードが読みにくい感じはしています。

お礼日時：2018/10/02 15:41

No.2 回答者： tknakamuri 回答日時： 2018/10/02 14:09

取り合えず、こんなかんじ。

Nが桁数ですが、10だと遅い(^-^;

標準ライブラリの itertools.permutations
でもできますね。