4年に一度のスポーツの祭典 全競技速報中

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

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

よろしくお願いします。

gooドクター

A 回答 (11件中1~10件)

正方行列のデターミネントを定義通りに計算する時に用いる関数で、n個の数値をすべての順列をある順番に並べた場合、k番目(k <= n!)の順列を返すものがありましたが、今、行方不明です。

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

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

今度は切り張りで作るバージョン
「順列の内容をすべて表示するプログラムにつ」の回答画像10
    • good
    • 0

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


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

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

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

これは利用するプログラミング言語に例えばマッピングに類する機能が無いと非常に面倒くさい問題ですよ。
そもそも、このテの問題は元々、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)
    • good
    • 0

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"]
とすれば、アルファベット26文字も可能です。(完了までに莫大な時間がかかると思いますが・・・)
    • good
    • 0

よこから失礼します。


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

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

そうすると、質問者の方も、そのソースをコピペできるので、確認がしやくすなるかと。
「順列の内容をすべて表示するプログラムにつ」の回答画像6
    • good
    • 0

もう少し綺麗なイメージ

「順列の内容をすべて表示するプログラムにつ」の回答画像5
    • good
    • 0

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

「順列の内容をすべて表示するプログラムにつ」の回答画像4
    • good
    • 0

AN02です。



いけね、Cのカテですね。pythonで書いてます(^-^;
変換するのは容易なので、御参考まで。
    • good
    • 0
この回答へのお礼

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

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

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



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

標準ライブラリの itertools.permutations
でもできますね。
「順列の内容をすべて表示するプログラムにつ」の回答画像2
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング