生成具有所有排列的序列 [英] generate sequence with all permutations
问题描述
如何生成包含所有可能排列的最短序列?
How can I generate the shortest sequence with contains all possible permutations?
示例:
对于长度2,答案为121,因为此列表包含12
Example: For length 2 the answer is 121, because this list contains 12 and 21, which are all possible permutations.
对于长度3,答案为123121321,因为此列表包含所有可能的排列:
123、231、312, 121(无效),213、132、321。
For length 3 the answer is 123121321, because this list contains all possible permutations: 123, 231, 312, 121 (invalid), 213, 132, 321.
每个数字(在给定的排列范围内)只能出现一次。
Each number (within a given permutation) may only occur once.
推荐答案
此贪婪算法会产生相当短的最小序列。
This greedy algorithm produces fairly short minimal sequences.
更新:请注意, n ≥的 6,此算法不会产生最短的字符串!
UPDATE: Note that for n ≥ 6, this algorithm does not produce the shortest possible string!
- 收集所有排列。
- 从集合中删除第一个排列。
- 让 a =第一个排列
- 在集合中查找与 a 的末端重叠最大的序列。如果有平局,则按字典顺序选择顺序为第一。从集合中删除选定的序列,并将不重叠的部分添加到 a 的末尾。重复此步骤,直到集合为空。
- Make a collection of all permutations.
- Remove the first permutation from the collection.
- Let a = the first permutation.
- Find the sequence in the collection that has the greatest overlap with the end of a. If there is a tie, choose the sequence is first in lexicographic order. Remove the chosen sequence from the collection and add the non-overlapping part to the end of a. Repeat this step until the collection is empty.
好奇的抢七步骤对于正确性是必不可少的。
The curious tie-breaking step is necessary for correctness; breaking the tie at random instead seems to result in longer strings.
我(通过编写更长,更慢的程序)验证了该算法给出的长度4的答案: 123412314231243121342132413214321,确实是最短的答案。但是,对于长度6,它会产生长度为873的答案,该长度比已知的最短解长。
I verified (by writing a much longer, slower program) that the answer this algorithm gives for length 4, 123412314231243121342132413214321, is indeed the shortest answer. However, for length 6 it produces an answer of length 873, which is longer than the shortest known solution.
算法为O( n ! 2 )。
Python中的实现:
An implementation in Python:
import itertools
def costToAdd(a, b):
for i in range(1, len(b)):
if a.endswith(b[:-i]):
return i
return len(b)
def stringContainingAllPermutationsOf(s):
perms = set(''.join(tpl) for tpl in itertools.permutations(s))
perms.remove(s)
a = s
while perms:
cost, next = min((costToAdd(a, x), x) for x in perms)
perms.remove(next)
a += next[-cost:]
return a
此函数生成的字符串的长度为1,3,9,33,153,873,5913,...似乎是此整数序列。
The length of the strings generated by this function are 1, 3, 9, 33, 153, 873, 5913, ... which appears to be this integer sequence.
我有预感,您可以比O( n ! 2 )做得更好。
I have a hunch you can do better than O(n!2).
这篇关于生成具有所有排列的序列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!