使用递归查找一组字符串中字符的所有可能排列 [英] Finding all possible permutations of the characters in a set of strings using recursion

问题描述

我有这组(希腊)字符串:

I have this set of (Greek) strings:

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

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

我想找到这 5 个字符串中字符的所有可能排列.例如，Ἰῇσοὺ、Ἰῇσοὖ、Ἰῇσου 等.我知道它应该涉及递归，因为字符串的数量不是固定的，但我是一个初学者，我完全被递归搞糊涂了.

I'd like to find all possible permutations of the characters in these 5 strings. For example, Ἰῇσοὺ, Ἰῇσοὖ, Ἰῇσου, etc. I know it should involve recursion since the number of strings is not fixed but I'm a beginner and I'm completely dumbfounded by recursion.

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

I did the following in Python and it does give me all combinations of the characters in each string. But I need the 'ἸἼΙἹἽ' to always come first, 'ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ' second,'σς' third, etc.

# -*- 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 中所做的:

Thanks for the help everybody. My mind is completely blown. Recursion! Here's what I ended up doing in 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()

推荐答案

只需写下五个嵌套循环即可.在伪代码中，

Just write down the five nested loops. In pseudocode,

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

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

To encode these five loops with recursion, so it's good for any number of input strings, again in pseudocode,

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 的保存位置，以及如何在 结束时将它们组合起来 -of-processing(基本上，您的两个选项是全局累加器或函数调用的参数).

Now you only need to figure out where to hold each current first-string's character ch and how to combine them all while at the end-of-processing (basically, your two options are a global accumulator, or an argument to a function invocation).

这篇关于使用递归查找一组字符串中字符的所有可能排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！