生成具有所有排列的序列 [英] 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 ！ ² ）。

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 ！ ² ）做得更好。

I have a hunch you can do better than O(n!²).

这篇关于生成具有所有排列的序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！