[解決済み] 文字列のすべての並べ換えのリストを生成する

質問

長さが x から y 文字の間の文字列で、文字の可変リストを含む、すべての可能な順列のリストを生成するにはどうしたらよいでしょうか。

どのような言語でも構いませんが、ポータブルであることが望ましいです。

解決方法は？

その方法はいくつかあります。一般的な方法は、再帰、メモ化、動的計画法を使う。基本的な考え方は、長さ1のすべての文字列のリストを生成し、各反復において、最後の反復で生成されたすべての文字列について、その文字列の各文字を連結したものを個別に追加する、というものです。(以下のコードの変数indexは、前回と次回の繰り返しの開始点を記録しています)

いくつかの疑似コード

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

この場合、長さが x よりも短い文字列をすべて削除する必要があり、それらはリストの最初の (x-1) * len(originalString) 項目になります。