给定特定条件的排列的Python实现

Question

如何在给定以下条件的情况下生成排列？

1. 有两个整数，例如。 1 和 4。
2. 给定的两个整数将成为排列的一部分，其中每个整数最多出现 N 次，每个排列的大小为 K。

假设 N = 3 和 K = 5，那么正确的结果应该是:

{1, 1, 1, 4, 4} , {1, 1, 4, 1, 4} , {4, 4, 4, 1, 1} , etc..

以下是无效或不正确结果的示例:

{1, 1, 1, 1, 4} -> 1 appear 4 times (1 should appear not greater than 3 times)

{1, 4, 4, 4, 1, 1} -> the size of the list is 6 (the size should be exactly 5)

此外，每个排列都应该是唯一的，这意味着没有重复。

我希望我能得到这个问题的最佳解决方案或算法。

提前致谢。 :)

Answer 1

看看这是否适合你

>>> K=5
>>> N=3
>>> src=[['1']*n+['4']*(K-n) for n in xrange(K-N,N+1)]
>>> set(x for s in src for x in itertools.permutations(s))
set([('1', '4', '1', '4', '1'), ('4', '1', '4', '1', '1'), ('1', '1', '4', '4', '4'), ('1', '4', '4', '1', '1'), ('1', '4', '4', '4', '1'), ('4', '4', '4', '1', '1'), ('4', '1', '1', '4', '1'), ('4', '4', '1', '4', '1'), ('1', '4', '1', '1', '4'), ('4', '1', '4', '4', '1'), ('1', '1', '4', '4', '1'), ('1', '4', '4', '1', '4'), ('4', '1', '4', '1', '4'), ('4', '1', '1', '1', '4'), ('4', '4', '1', '1', '4'), ('1', '4', '1', '4', '4'), ('1', '1', '4', '1', '4'), ('4', '4', '1', '1', '1'), ('4', '1', '1', '4', '4'), ('1', '1', '1', '4', '4')])

注意**

首先用“1”和“4”创建所有可能的组合。请注意特定整数的最大 N 个实例的限制，因此在一组 K 个数字中，如果有 i 个 x 实例，则两个数字 (x,y) 有 (K-i) 个 y 实例。在那种情况下，i 和 x 都应该在 [K-N,N] 范围内。

现在下一步是使用生成器理解来创建上述集合的所有可能实例的所有可能迭代。我正在使用集合理解来删除任何重复项，并使用生成器来不存储中间重复结果。