文字の可変リストを含む、長さが x 文字と y 文字の間の文字列の可能なすべての順列のリストを生成するにはどうすればよいでしょうか。
どの言語でも機能しますが、移植可能でなければなりません。
質問する
209863 次
36 に答える
69
これを行うにはいくつかの方法があります。一般的な方法では、再帰、メモ化、または動的計画法を使用します。基本的な考え方は、長さ 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) エントリになります。
于 2008-08-02T07:48:07.607 に答える
40
バックトラックを使用することをお勧めします
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp;
temp = *a;
*a = *b;
*b = temp;
}
void print(char *a, int i, int n) {
int j;
if(i == n) {
printf("%s\n", a);
} else {
for(j = i; j <= n; j++) {
swap(a + i, a + j);
print(a, i + 1, n);
swap(a + i, a + j);
}
}
}
int main(void) {
char a[100];
gets(a);
print(a, 0, strlen(a) - 1);
return 0;
}
于 2012-01-10T18:00:20.177 に答える
26
あなたはたくさんの文字列を手に入れるつもりです、それは確かです...
ここで、xとyはそれらを定義する方法であり、rは選択する文字数です-私があなたを正しく理解している場合。必要に応じてこれらを確実に生成し、だらしなくして、パワーセットを生成してから文字列の長さをフィルタリングする必要があります。
以下は間違いなくこれらを生成するための最良の方法ではありませんが、それでもなお興味深いものです。
Knuth（第4巻、筋肉束2、7.2.1.3）は、（s、t）-組み合わせは、繰り返して一度にtをとるs + 1ものと同等であることを示しています-（s、t）-組み合わせは、に等しいKnuth 。これは、最初に各（s、t）-組み合わせをバイナリ形式（つまり、長さ（s + t））で生成し、各1の左側にある0の数を数えることで理解できます。
10001000011101->順列になります：{0、3、4、4、4、1}
于 2008-08-05T04:57:52.987 に答える
15
Knuth による非再帰的なソリューション、Python の例:
def nextPermutation(perm):
k0 = None
for i in range(len(perm)-1):
if perm[i]<perm[i+1]:
k0=i
if k0 == None:
return None
l0 = k0+1
for i in range(k0+1, len(perm)):
if perm[k0] < perm[i]:
l0 = i
perm[k0], perm[l0] = perm[l0], perm[k0]
perm[k0+1:] = reversed(perm[k0+1:])
return perm
perm=list("12345")
while perm:
print perm
perm = nextPermutation(perm)
于 2010-11-09T13:58:06.167 に答える
13
これがC＃の簡単な解決策です。
特定の文字列の個別の順列のみを生成します。
static public IEnumerable<string> permute(string word)
{
if (word.Length > 1)
{
char character = word[0];
foreach (string subPermute in permute(word.Substring(1)))
{
for (int index = 0; index <= subPermute.Length; index++)
{
string pre = subPermute.Substring(0, index);
string post = subPermute.Substring(index);
if (post.Contains(character))
continue;
yield return pre + character + post;
}
}
}
else
{
yield return word;
}
}
于 2010-07-05T09:06:37.387 に答える
13
長さ x から y までの N 文字のすべてのサブセットをすばやく生成するために、「セットのサブセットを効率的に列挙する」を参照してください。C での実装が含まれています。
サブセットごとに、すべての順列を生成する必要があります。たとえば、「abcde」から 3 文字が必要な場合、このアルゴリズムでは「abc」、「abd」、「abe」が得られますが、「acb」、「bac」、 「bca」など
于 2008-11-14T19:36:49.200 に答える
13
Sarp の回答に基づくいくつかの動作する Java コード:
public class permute {
static void permute(int level, String permuted,
boolean used[], String original) {
int length = original.length();
if (level == length) {
System.out.println(permuted);
} else {
for (int i = 0; i < length; i++) {
if (!used[i]) {
used[i] = true;
permute(level + 1, permuted + original.charAt(i),
used, original);
used[i] = false;
}
}
}
}
public static void main(String[] args) {
String s = "hello";
boolean used[] = {false, false, false, false, false};
permute(0, "", used, s);
}
}
于 2010-04-04T18:18:01.510 に答える
8
C++ での再帰的ソリューション
int main (int argc, char * const argv[]) {
string s = "sarp";
bool used [4];
permute(0, "", used, s);
}
void permute(int level, string permuted, bool used [], string &original) {
int length = original.length();
if(level == length) { // permutation complete, display
cout << permuted << endl;
} else {
for(int i=0; i<length; i++) { // try to add an unused character
if(!used[i]) {
used[i] = true;
permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
used[i] = false;
}
}
}
于 2008-09-29T01:34:58.510 に答える
8
これは、Mike の Ruby バージョンを Common Lisp に翻訳したものです。
(defun perms (x y original-string)
(loop with all = (list "")
with current-array = (list "")
for iteration from 1 to y
do (loop with next-array = nil
for string in current-array
do (loop for c across original-string
for value = (concatenate 'string string (string c))
do (push value next-array)
(push value all))
(setf current-array (reverse next-array)))
finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))
そして、少し短く、より多くのループ機能機能を使用する別のバージョン:
(defun perms (x y original-string)
(loop repeat y
collect (loop for string in (or (car (last sets)) (list ""))
append (loop for c across original-string
collect (concatenate 'string string (string c)))) into sets
finally (return (loop for set in sets
append (loop for el in set when (>= (length el) x) collect el)))))
于 2008-09-16T05:15:26.813 に答える
8
C# の再帰的ソリューションの簡単な単語を次に示します。
方法：
public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
{
bool finished = true;
ArrayList newWords = new ArrayList();
if (words.Count == 0)
{
foreach (string letter in letters)
{
words.Add(letter);
}
}
for(int j=index; j<words.Count; j++)
{
string word = (string)words[j];
for(int i =0; i<letters.Length; i++)
{
if(!word.Contains(letters[i]))
{
finished = false;
string newWord = (string)word.Clone();
newWord += letters[i];
newWords.Add(newWord);
}
}
}
foreach (string newWord in newWords)
{
words.Add(newWord);
}
if(finished == false)
{
CalculateWordPermutations(letters, words, words.Count - newWords.Count);
}
return words;
}
呼び出し:
string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
于 2008-10-20T00:17:50.220 に答える
8
私はRubyでこれを素早く作り上げました：
def perms(x, y, possible_characters)
all = [""]
current_array = all.clone
1.upto(y) { |iteration|
next_array = []
current_array.each { |string|
possible_characters.each { |c|
value = string + c
next_array.insert next_array.length, value
all.insert all.length, value
}
}
current_array = next_array
}
all.delete_if { |string| string.length < x }
end
組み込みの順列型関数の言語 API を調べると、より最適化されたコードを記述できる可能性がありますが、数値が非常に高い場合は、多くの結果を得る方法があまりないかどうかわかりません。 .
とにかく、コードの背後にある考え方は、長さ 0 の文字列から始めて、長さ Z のすべての文字列を追跡することです。ここで、Z は反復の現在のサイズです。次に、各文字列を調べて、各文字を各文字列に追加します。最後に、x しきい値を下回ったものをすべて削除し、結果を返します。
無意味な可能性のある入力 (null 文字リスト、x と y の奇妙な値など) ではテストしませんでした。
于 2008-08-02T07:56:07.933 に答える
8
permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[( *B C), (C B* )] -> [( *A BC ), (B A C), (BC A* ), ( *A CB), (C A B), (CB A* )] 各アルファベットチェックを挿入するときに重複を削除するには、前の文字列が同じアルファベットで終わっているかどうかを確認します(なぜ? -演習)
public static void main(String[] args) {
for (String str : permStr("ABBB")){
System.out.println(str);
}
}
static Vector<String> permStr(String str){
if (str.length() == 1){
Vector<String> ret = new Vector<String>();
ret.add(str);
return ret;
}
char start = str.charAt(0);
Vector<String> endStrs = permStr(str.substring(1));
Vector<String> newEndStrs = new Vector<String>();
for (String endStr : endStrs){
for (int j = 0; j <= endStr.length(); j++){
if (endStr.substring(0, j).endsWith(String.valueOf(start)))
break;
newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
}
}
return newEndStrs;
}
重複を除くすべての順列を出力します
于 2011-02-22T18:45:03.570 に答える
8
...そしてここにCバージョンがあります：
void permute(const char *s, char *out, int *used, int len, int lev)
{
if (len == lev) {
out[lev] = '\0';
puts(out);
return;
}
int i;
for (i = 0; i < len; ++i) {
if (! used[i])
continue;
used[i] = 1;
out[lev] = s[i];
permute(s, out, used, len, lev + 1);
used[i] = 0;
}
return;
}
于 2011-02-07T21:56:58.350 に答える
7
動作するRubyの答え：
class String
def each_char_with_index
0.upto(size - 1) do |index|
yield(self[index..index], index)
end
end
def remove_char_at(index)
return self[1..-1] if index == 0
self[0..(index-1)] + self[(index+1)..-1]
end
end
def permute(str, prefix = '')
if str.size == 0
puts prefix
return
end
str.each_char_with_index do |char, index|
permute(str.remove_char_at(index), prefix + char)
end
end
# example
# permute("abc")
于 2012-04-20T00:21:53.210 に答える
7
次の Java 再帰は、指定された文字列のすべての順列を出力します。
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() != 0){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
System.out.println(str1);
}
}
以下は、n! を作成する上記の「permut」メソッドの更新バージョンです。(n factorial) 上記の方法に比べて再帰呼び出しが少ない
//call it as permut("",str);
public void permut(String str1,String str2){
if(str2.length() > 1){
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}else{
char ch = str2.charAt(0);
for(int i = 0; i <= str1.length();i++)
System.out.println(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
str2.substring(1,str2.length()));
}
}
于 2013-06-19T04:23:42.563 に答える
7
Perl では、小文字のアルファベットに制限したい場合は、次のようにします。
my @result = ("a" .. "zzzz");
これにより、小文字を使用した 1 ～ 4 文字のすべての可能な文字列が得られます。大文字の場合は、とに変更"a"します。"A""zzzz""ZZZZ"
大文字と小文字が混在する場合は、はるかに難しくなり、そのような Perl の組み込み演算子の 1 つではおそらく実行できません。
于 2009-02-15T10:02:43.563 に答える
6
import java.util.*;
public class all_subsets {
public static void main(String[] args) {
String a = "abcd";
for(String s: all_perm(a)) {
System.out.println(s);
}
}
public static Set<String> concat(String c, Set<String> lst) {
HashSet<String> ret_set = new HashSet<String>();
for(String s: lst) {
ret_set.add(c+s);
}
return ret_set;
}
public static HashSet<String> all_perm(String a) {
HashSet<String> set = new HashSet<String>();
if(a.length() == 1) {
set.add(a);
} else {
for(int i=0; i<a.length(); i++) {
set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
}
}
return set;
}
}
于 2010-10-24T22:01:36.817 に答える
5
そもそもなぜこれをやりたいのかわかりません。x と y の適度に大きな値の結果のセットは巨大になり、x や y が大きくなるにつれて指数関数的に大きくなります。
考えられる文字のセットがアルファベットの小文字 26 文字であり、長さ = 5 のすべての順列を生成するようにアプリケーションに要求するとします。メモリが不足しないと仮定すると、11,881,376 (つまり、26 のべき乗) が得られます。の 5) 弦を戻します。その長さを 6 まで上げると、308,915,776 個の弦が返されます。これらの数値は、非常に急速に、痛ましいほど大きくなります。
これが私がJavaでまとめたソリューションです。2 つの実行時引数 (x と y に対応) を指定する必要があります。楽しむ。
public class GeneratePermutations {
public static void main(String[] args) {
int lower = Integer.parseInt(args[0]);
int upper = Integer.parseInt(args[1]);
if (upper < lower || upper == 0 || lower == 0) {
System.exit(0);
}
for (int length = lower; length <= upper; length++) {
generate(length, "");
}
}
private static void generate(int length, String partial) {
if (length <= 0) {
System.out.println(partial);
} else {
for (char c = 'a'; c <= 'z'; c++) {
generate(length - 1, partial + c);
}
}
}
}
于 2008-08-02T09:40:54.693 に答える
5
これは、私が思いついた非再帰的なバージョンで、javascript です。要素の交換にはいくつかの類似点がありますが、上記の Knuth の非再帰的なものに基づいていません。最大 8 要素の入力配列の正確性を確認しました。
簡単な最適化は、配列をプリフライトしてout回避することpush()です。
基本的な考え方は次のとおりです。
単一のソース配列が与えられた場合、最初の要素を後続の各要素と順番に交換する最初の新しい配列セットを生成し、そのたびに他の要素を摂動させません。例: 1234 が与えられた場合、1234、2134、3214、4231 を生成します。
前のパスの各配列を新しいパスのシードとして使用しますが、最初の要素を交換する代わりに、2 番目の要素を後続の各要素と交換します。また、今回は元の配列を出力に含めないでください。
完了するまで手順 2 を繰り返します。
コードサンプルは次のとおりです。
function oxe_perm(src, depth, index)
{
var perm = src.slice(); // duplicates src.
perm = perm.split("");
perm[depth] = src[index];
perm[index] = src[depth];
perm = perm.join("");
return perm;
}
function oxe_permutations(src)
{
out = new Array();
out.push(src);
for (depth = 0; depth < src.length; depth++) {
var numInPreviousPass = out.length;
for (var m = 0; m < numInPreviousPass; ++m) {
for (var n = depth + 1; n < src.length; ++n) {
out.push(oxe_perm(out[m], depth, n));
}
}
}
return out;
}
于 2011-08-03T07:11:34.030 に答える
3
私は今日これを必要としていました、そしてすでに与えられた答えは私を正しい方向に向けましたが、それらは私が望んでいたものではありませんでした。
これは、ヒープのメソッドを使用した実装です。配列の長さは少なくとも3でなければならず、実際的な考慮事項としては、実行したいこと、忍耐力、およびクロック速度に応じて、10程度以下にする必要があります。
ループに入る前にPerm(1 To N)、最初の順列、Stack(3 To N)ゼロ*、および**Levelで初期化します。2ループ呼び出しの最後に、NextPerm完了時にfalseを返します。
*VBがあなたに代わってそれを行います。
** NextPermを少し変更してこれを不要にすることができますが、このように明確になります。
Option Explicit
Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
Swap Perm(1), Perm(2)
Level = 3
Else
While Stack(Level) = Level - 1
Stack(Level) = 0
If Level = UBound(Stack) Then Exit Function
Level = Level + 1
Wend
Stack(Level) = Stack(Level) + 1
If Level And 1 Then N = 1 Else N = Stack(Level)
Swap Perm(N), Perm(Level)
Level = 2
End If
NextPerm = True
End Function
Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub
'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
If CurrentY + TextHeight("0") > ScaleHeight Then
ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
CurrentY = 0
CurrentX = 0
End If
T = vbNullString
For I = 1 To UBound(A)
Print A(I);
T = T & Hex(A(I))
Next
Print
Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
J = J * I
Next
If J <> Test.Count Then Stop
End Sub
他の方法は、さまざまな著者によって説明されています。Knuthは2つを説明しています。1つは辞書式順序を示しますが、複雑で低速であり、もう1つは単純な変更の方法として知られています。JieGaoとDianjunWangも興味深い論文を書きました。
于 2011-10-02T09:13:57.093 に答える
3
ルビーで：
str = "a"
100_000_000.times {puts str.next!}
かなり高速ですが、時間がかかります =)。もちろん、短い文字列が気に入らない場合は、「aaaaaaaa」から始めることもできます。
ただし、実際の質問を誤解している可能性があります-投稿の1つでは、文字列のブルートフォースライブラリが必要なように聞こえましたが、主な質問では、特定の文字列を並べ替える必要があるように聞こえます.
あなたの問題はこれに多少似ています: http://beust.com/weblog/archives/000491.html (数字が繰り返されないすべての整数をリストします。その結果、多くの言語がそれを解決し、順列を使用する ocaml の人、およびさらに別のソリューションを使用する Java の人)。
于 2008-09-15T17:32:15.787 に答える
2
Python のこのコードは、最大 4 文字にallowed_characters設定して呼び出すと[0,1]、2^4 の結果が生成されます。
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
def generate_permutations(chars = 4) :
#modify if in need!
allowed_chars = [
'0',
'1',
]
status = []
for tmp in range(chars) :
status.append(0)
last_char = len(allowed_chars)
rows = []
for x in xrange(last_char ** chars) :
rows.append("")
for y in range(chars - 1 , -1, -1) :
key = status[y]
rows[x] = allowed_chars[key] + rows[x]
for pos in range(chars - 1, -1, -1) :
if(status[pos] == last_char - 1) :
status[pos] = 0
else :
status[pos] += 1
break;
return rows
import sys
print generate_permutations()
これがお役に立てば幸いです。数字だけでなく、あらゆる文字に対応
于 2011-05-26T14:22:12.887 に答える
0
ドライバーmain()メソッドを使用した再帰的ソリューション。
public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
if(remaining.length()==0)
System.out.println(newstring);
for(int i=0; i<remaining.length(); i++) {
String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
stringPermutations(newstring+remaining.charAt(i), newRemaining);
}
}
public static void main(String[] args) {
String string = "abc";
AllPermutationsOfString.stringPermutations("", string);
}
}
于 2013-10-19T01:34:11.233 に答える
0
Java 言語用に書かれたコード:
パッケージ namo.algorithms;
java.util.Scanner をインポートします。
公開クラス順列 {
public static int totalPermutationsCount = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("input string : ");
String inputString = sc.nextLine();
System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
findPermuationsOfString(-1, inputString);
System.out.println("**************************************");
System.out.println("total permutation strings ==> "+totalPermutationsCount);
}
public static void findPermuationsOfString(int fixedIndex, String inputString) {
int currentIndex = fixedIndex +1;
for (int i = currentIndex; i < inputString.length(); i++) {
//swap elements and call the findPermuationsOfString()
char[] carr = inputString.toCharArray();
char tmp = carr[currentIndex];
carr[currentIndex] = carr[i];
carr[i] = tmp;
inputString = new String(carr);
//System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
if(currentIndex == inputString.length()-1) {
totalPermutationsCount++;
System.out.println("permuation string ==> "+inputString);
} else {
//System.out.println("in else block>>>>");
findPermuationsOfString(currentIndex, inputString);
char[] rarr = inputString.toCharArray();
char rtmp = carr[i];
carr[i] = carr[currentIndex];
carr[currentIndex] = rtmp;
inputString = new String(carr);
}
}
}
}
于 2016-06-05T08:42:14.117 に答える
0
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list
def func( x,i,j ): #returns x[i..j]
z = ''
for i in range(i,j+1):
z = z+x[i]
return z
def perm( x , length , list ): #perm function
if length == 1 : # base case
list.append( x[len(x)-1] )
return list
else:
lists = perm( x , length-1 ,list )
lists_temp = lists #temporarily storing the list
lists = []
for i in range( len(lists_temp) ) :
list_temp = gen(lists_temp[i],x[length-2],lists)
lists += list_temp
return lists
于 2013-08-22T17:51:53.097 に答える
0
これはあなたの質問に正確に答えるものではありませんが、同じ長さの多数の文字列から文字のすべての順列を生成する 1 つの方法を次に示します。たとえば、単語が「コーヒー」、「joomla」、および「moodle」の場合、 「coodle」、「joodee」、「joffle」などの出力が期待されます。
基本的に、組み合わせの数は、(単語数) の (1 単語あたりの文字数) 乗です。したがって、0 と組み合わせの数 - 1 の間の乱数を選択し、その数を基数 (単語数) に変換してから、その数の各桁を、次の文字を取得する単語の指標として使用します。
例: 上記の例。3単語6文字＝729通りの組み合わせ。乱数を選択してください: 465. 基数 3 に変換します: 122020. 単語 1 の最初の文字、単語 2 の 2 番目、単語 2 の 3 番目、単語 0 の 4 番目の文字を取得します...すると、... "joofle" が得られます。
すべての順列が必要な場合は、0 から 728 までループするだけです。もちろん、ランダムな値を 1 つだけ選択する場合は、文字をループすることで、混乱を避けることができます。このメソッドを使用すると、すべての順列が必要な場合に再帰を回避できます。さらに、数学(tm)を知っているように見えます。
組み合わせの数が多すぎる場合は、一連の小さな単語に分割し、最後にそれらを連結できます。
于 2008-09-16T05:33:25.930 に答える
0
def permutation(str)
posibilities = []
str.split('').each do |char|
if posibilities.size == 0
posibilities[0] = char.downcase
posibilities[1] = char.upcase
else
posibilities_count = posibilities.length
posibilities = posibilities + posibilities
posibilities_count.times do |i|
posibilities[i] += char.downcase
posibilities[i+posibilities_count] += char.upcase
end
end
end
posibilities
end
これが非再帰的なバージョンに対する私の見解です
于 2014-01-23T03:28:19.943 に答える
0
pythonic ソリューション:
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
于 2014-07-13T07:51:36.230 に答える