满足特定条件的Python全排列实现

3 投票

4 回答

1206 浏览

数据工程师

提问于 2025-04-17 08:28

我想知道如何在以下条件下生成排列。

有两个整数，比如说1和4。
这两个整数会出现在排列中，每个整数最多出现N次，而每个排列的大小是K。

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

{1, 1, 1, 4, 4} , {1, 1, 4, 1, 4} , {4, 4, 4, 1, 1}，等等。

以下是无效或错误的结果示例：

{1, 1, 1, 1, 4} -> 1出现了4次（1最多只能出现3次）

{1, 4, 4, 4, 1, 1} -> 列表的大小是6（大小应该正好是5）

另外，每个排列应该是独一无二的，也就是说不能有重复的排列。

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

提前谢谢大家。:)

递归唯一性算法设计组合数学约束条件整数限制排列生成排列优化

4 个回答

这是一个思考问题的方法，不过我在想有没有更优雅的解决方案：

假设 N = 3 和 K = 5，就像上面那样。为了避免混淆，我将用 a 和 b 来代替你的 '1' 和 '4' :P

因为每个符号（a 或 b）最多只能出现 3 次，这意味着我们想要得到以下组合的所有排列：

在 5 个 b 中放 2 个 a
在 5 个 b 中放 3 个 a

所以我们只需要找到 {a,a,b,b,b} 和 {a,a,a,b,b} 的所有排列。

一般来说，你只需要找到 {m 个 a 和 (K-m) 个 b} 的排列，其中 m 的取值范围是 { K-N, K-N+1, K-N+2, ... N }。

实现这个的一个方法是：

设置 N 和 K。
设置 m = K-N。
创建一个长度为 K 的列表，里面全是 b，叫它 x。
创建一个索引列表，索引范围是 0,1,2,..,K-1，然后找出所有长度为 m 的子集。这些子集就是我们放置 a 的位置。
对 m = K-N, K-N+1, ... , N 重复以上步骤。

在第 4 步中，我们使用模块 itertools，特别是 itertools.combinations。

所以：

import itertools

def notQuitePermutations(N,K,symbol1,symbol2):
    permutations = []
    base_perm = [symbol2]*K # step 3
    for m in range(K-N,N+1): # +1 so we *include* N
        # step 4: find m places to put symbol1 in.
        idxs = itertools.combinations(range(K),m)
        for idx in idxs:
            perm = base_perm[:] # make a copy of base_perm
            for i in idx:
                perm[i] = symbol1 # put symbol1 in.
            # add this permutation to the list
            permutations += [perm]
    return permutations

然后：

>>> notQuitePermutations(3,5,1,4)
[[1, 1, 4, 4, 4], [1, 4, 1, 4, 4], [1, 4, 4, 1, 4],....

另一种选择是使用 itertools.permutations 找到 {m 个符号1 和 (K-m) 个符号2} 的所有排列。不过这样会出现重复的排列（因为 Python 的排列是基于元素的唯一位置，而不是元素的唯一值）。所以你需要在之后过滤掉这些重复，这在 K 和 N 较大时可能会变得很麻烦。这就是我选择上面方法的原因，因为它没有重复的问题。

回答于 2025-04-17 由 Python大师

分享举报

从这里开始（就像Abhijit的回答中提到的）...

>>> K=5
>>> N=3
>>> [['1']*n+['4']*(K-n) for n in xrange(K-N,N+1)]
[['1', '1', '4', '4', '4'], ['1', '1', '1', '4', '4']]

...你可以为每个列表生成包含重复元素的排列。另外，如果N小于K-N，可以考虑通过设置N=max(N,K-N)来处理这种情况。

回答于 2025-04-17 由 Python大师

分享举报

看看这个对你有没有用

>>> 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，那么剩下的(K-i)个数字就得是y（x和y是两个不同的数字）。在这种情况下，i和x的数量都应该在[K-N, N]这个范围内。

接下来的步骤是使用生成器表达式来创建上述组合中所有可能的排列。我使用集合表达式来去掉重复的组合，同时用生成器来避免存储中间的重复结果。

回答于 2025-04-17 由 Python大师

分享举报

满足特定条件的Python全排列实现

4 个回答

撰写回答