具有替换和最大出现约束的组合

Question

from itertools import *
import collections
for i in combinations_with_replacement(['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'],15):
    b = (''.join(i))
    freq = collections.Counter(b)
    for k in freq:
        if freq [k] < 5:
            print(k)

此代码最多打印字符，如果小于 5 个则算作什么

我尝试做的是，如果在该字符串的任何位置重复了小于 x 次的任何字符，并仅打印符合该条件的字符串。

问题不在于我尝试做什么，或其全部打印并忽略 if ... 或打印 notting。如何做对，或者可能在 python 存在简单的解决方案？

结果最多以小于5为例

False - fffaaffbbdd ( repeat 5 titemes f)
False - fffffaaaaac ( repeat 5 times a and f)
True -  aaabbbccc11 ( no any character repeated more than 4 times )

更清楚地解释问题 - 在提供给下一个函数之前过滤所有字符重复次数超过 x 的字符串。例如 - 有简单的 print that strings ，而不是 print strings what not at rule.

Answer 1

如果我没理解错的话，您想打印每个字符最多只出现 4 次的字符串：

from collections import Counter
from itertools import combinations_with_replacement


for i in combinations_with_replacement(['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'],15):
    c = Counter(i)
    if c.most_common(1)[0][1] > 4:
        continue
    print(''.join(i))

打印：

...

00002446899cccd
00002446899ccce
00002446899cccf
00002446899ccdd

...

Answer 2

一种更具建设性的方法（意思是：我不会遍历所有可能的组合 - 我直接构建有效组合）。

您需要安装 sympy 才能运行。

在这个例子中我只使用了元素 "abcdef" 并且限制重复次数严格小于 MAX = 4。我将要输出的字符串的长度固定在 M = 6.

我首先获取 M 的所有 partitions，重复次数有限 k=MAX - 1，并且不超过 m=N 个部分。我立即将它们转换为列表：

{3: 2} [3, 3, 0, 0, 0, 0]
{3: 1, 2: 1, 1: 1} [3, 2, 1, 0, 0, 0]
{3: 1, 1: 3} [3, 1, 1, 1, 0, 0]
{2: 3} [2, 2, 2, 0, 0, 0]
{2: 2, 1: 2} [2, 2, 1, 1, 0, 0]
{2: 1, 1: 4} [2, 1, 1, 1, 1, 0]
{1: 6} [1, 1, 1, 1, 1, 1]

在这些列表中，我迭代了多重排列 - 我的意思是那些代表我 select 的元素以及它们重复的频率：例如：

[2, 1, 2, 0, 0, 1] -> "aabccf"  # 2*"a", 1*"b", ..., 0*"e", 1*"f"

你想要的结果就是这些字符串的多重排列。

from sympy.utilities.iterables import multiset_permutations, partitions

MAX = 4  # (all counts < MAX)
elements = "abcdef"
N = len(elements)
M = 6  # output length


def dict_to_list(dct, N):
    ret = [0] * N
    j = 0
    for k, v in dct.items():
        ret[j:j + v] = [k] * v
        j += v
    return ret


for dct in partitions(M, k=MAX - 1, m=N):
    lst = dict_to_list(dct, N)
    for part in multiset_permutations(lst):
        el = ''.join(n * v for n, v in zip(part, elements))
        for msp in multiset_permutations(el):
            print(''.join(msp))

对于您的情况，您需要更改：

MAX = 5  # (all counts < MAX)
elements = "0123456789abcdef"
M = 15  # output length

但它的复杂性很大（但比最初的方法好得多）！

具有替换和最大出现约束的组合

Combinations with Replacement and maximal Occurrence Constraint

python

itertools

python-3.x

python-collections

python-3.6