使用递归查找一组字符串中字符的所有可能排列

Question

我有这组（希腊语）字符串：

ἸἼΙἹἽ, ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ, σς, οὸόὀὄὅὂ, ὺὖυῦύὐὑὔϋὕὗὓὒῢ

我想找出这 5 个字符串中字符的所有可能排列。比如Ἰῇσοὺ, Ἰῇσοὖ, Ἰῇσου等。我知道应该涉及到递归，因为字符串的个数不固定，但我是初学者，完全被递归吓傻了。

我在 Python 中执行了以下操作，它确实为我提供了每个字符串中字符的所有组合。但是我需要'ἸἼΙἹἽ'总是第一位，'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ'第二，'σς'第三，等等

# -*- coding: utf-8 -*-

def Gen( wd, pos, chars ):
    if pos < len( chars ):
        for c in chars:
            for l in c:
                Gen( wd + l, pos + 1, chars )
    else:
        print wd

chars = [ u'ἸἼΙἹἽ', u'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ', u'σς', u'οὸόὀὄὅὂ', u'ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ' ]

Gen( "", 0, chars )

感谢大家的帮助。我的心完全被炸毁了。递归！这是我最终在 Python 中所做的事情：

# -*- coding: utf-8 -*-

s = [ u'ἸἼΙἹἽ', u'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ', u'σς', u'οὸόὀὄὅὂ', u'ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ' ]

results = []

def recur( wd, strings ):
    index = 0
    if index < len( strings ):
        for c in strings[ index ]:
            recur( wd + c, strings[ index + 1: ] )
    else:
        results.append( wd )

def main():
    recur( '', s )
    for r in results:
        print r.encode( 'utf-8' )

main()

Answer 1

您创建一个 char 数组，其中将包含您要使用的字符串 char str[] = "ABC";

然后你得到字符串的长度int n = strlen(str);，最后你排列。

您创建了一个新函数，它将包含输入字符串、字符串的起始索引和字符串的结束索引。检查起始索引 (int s) 是否等于结束索引 (int e) 如果是，那意味着你完成了，如果不是，你进入一个循环，从开始（s）到结束（e），交换值，递归，再次交换回溯。

C++ 示例：

#include <stdio.h>
#include <string.h>

void swap(char *i, char *j)
{
    char temp;
    temp = *i;
    *i = *j;
    *j = temp;
}

void permutate(char *str, int start, int end)
{
    int i;
    if (start == end)
        printf("%s\n", str);
    else
    {
        for (i = start; i <= end; i++)
        {
            swap((str + start), (str + i));
            permutate(str, start + 1, end);
            swap((str + start), (str + i)); //backtrack
        }
    }
}

int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permutate(str, 0, n - 1);
    return 0;
}

我对 Python 不太熟悉，但我发现了一些可能对您的情况有所帮助的内容：

def comb(first_str, second_str):
if not first_str:
    yield second_str
    return
if not second_str:
    yield first_str
    return

for result in comb(first_str[1:], second_str):
    yield first_str[0] + result
for result in comb(first_str, second_str[1:]):
    yield second_str[0] + result

>>> for result in comb("ἸἼΙἹἽ", "ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ"):
print(result)

Answer 2

只需记下五个嵌套循环。在伪代码中，

for a in "ἸἼΙἹἽ"
  for b in "ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ"
    for c in "σς"
      for d in "οὸόὀὄὅὂ"
        for e in "ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ"
           emit [a,b,c,d,e]

用递归对这五个循环进行编码，因此它适用于任意数量的输入字符串，同样是伪代码，

g(list-of-strings) =
   | case list-of-strings
   | of  empty --> end-of-processing
   | of  (first-string AND rest-of-strings) --> 
            for each ch in first-string 
               DO g(rest-of-strings)

现在你只需要弄清楚每个当前 first-string 的角色 ch 的位置以及如何在 end-of-processing 处将它们组合起来（基本上，你的两个选择是全局累加器，或函数调用的参数）。

使用递归查找一组字符串中字符的所有可能排列

Finding all possible permutations of the characters in a set of strings using recursion

recursion

permutation