排列列出随机结果

Question

有人可以帮助使用此代码，我需要它能够保存每个排列列表和每个数字，并打印随机的时间，让我们说20个。

现在，它仅适用于第一部分。 它打印了一个给定单词的排列，但是我不知道要整合所评论的下半部分，它必须进行计数并随机结果。

假设您需要“小鼠”的排列，应该出现24行，这应该是代码后半段的输入（最后6行）。使用sys.stdin，必须将这24行添加到计数列表中。结果，每行都会获取一个数字（1-24），然后将其中的20行随机选择（必须随机使用，必须随机使用）。

输入是一个单词， 输出必须为20个随机排列。

任何建议将不胜感激，谢谢。

import sys, re



def gen_permutations(a, n):
 
    if n == 0:
        print(''.join(a))
    else:
        for i in range(n):
            gen_permutations(a, n-1)
            j = 0 if n % 2 == 0 else i
            a[j], a[n] = a[n], a[j]
        gen_permutations(a, n-1)

if len(sys.argv) != 2:
    sys.stderr.write('one argument only\n')
    sys.exit(1)


word = sys.argv[1]

gen_permutations(list(word), len(word)-1)

#counts = {}
#for line in sys.stdin:
#     for word in re.findall(r'[a-z\']+', line.lower()):
#         counts[word] = counts.get(word, 0) + 1
#         for word, count in sorted(counts.items()):
#             print (word, count)

Answer 1

作为替代答案，从更数学的角度来解决如何解决此问题：

from math import factorial
from random import sample


def solve(word, count):
    factorials = [factorial(x) for x in range(len(word))][::-1]
    indices = sample(range(factorial(len(word))), count)
    
    output = []
    for index in indices:
        alphabet = list(word)
        result = ""
        for fact in factorials:
            q, index = divmod(index, fact)
            result += alphabet.pop(q)
        output.append(result)
    return output

示例用法

>>> print(solve("abcde", 10))
['bdeca', 'bdcea', 'decba', 'caebd', 'daceb', 'cedba', 'cdbea', 'ebcda', 'decab', 'becad']

通过首先选择选择排列索引的方式，并计算与这些索引相关的排列。 n字符的排列具有n！排列，因此，如果我们的索引大于该索引，我们将需要附加字符。我们（从概念上）交换领先字符，减去我们跳过的n！排列，看看此新索引值是否小于n！ - 冲洗并重复直到这是。然后，我们重复n-1，依此类推，直到我们构建了整个排列，然后为其余的索引进行操作。

索引映射i使用的相当于itertools.permutations的顺序，如果您有indices 的 [2，5，5，9] ，输出将与列表的2、5和9'元素相同（排列（...））。

对于小样本量，此实现的速度要快得多，因为它的时间复杂性为o（c​​ * s） - 至少如果您使用足够小的数字，可以将乘法视为o（1）。否则，该阶乘预报将是时间复杂性的不可忽视的部分。

如果您需要按顺序排序的顺序，则可以在迭代之前对indices进行排序，并且结果将按顺序返回。

Answer 2

from itertools import permutations
from random import sample

word = ...

perms = sample(list(enumerate(permutations(word))), 20)
for id_val, perm in perms:
    print("".join(perm), id_val)

单词“ abcd”的输出：

bcad 8
bdca 11
cdba 17
cbad 14
acdb 3
adcb 5
abcd 0
dbac 20
dbca 21
cabd 12
abdc 1
bacd 6
cbda 15
cadb 13
badc 7
bdac 10
cdab 16
dcba 23
dcab 22
dacb 19

注释：此（以及您的原始实现）会生成所有排列，即使是在输出中未使用的排列。这意味着对于大单词，在本质上是O（n！），跑步将比必要的时间更长。

如果发现遇到性能问题，则应使用Random.Choices选择20 indices ，然后生成对应的与这些指数相对应的特定排列。您会找到Math.comb和Math.factorial对此有用。

---

要计算重复序列，您需要random.sample to random.choices（允许重复），然后使用collections.counter.counter计算他们。

from itertools import permutations
from random import choices
from collections import Counter

perms = choices(list(enumerate(permutations(word))), k=20)
counts = Counter(counts)

for perm, count in counts.items():
    print("".join(perm), count)