生成独特数字组合的方法

Question

我有一个数组：

A = [0,2,5,6]
B = [5,6,8,9]
C = [6,7,8,9]

我想写两个函数，具体如下：

---

问题1 当我传入上面定义的任何一个数组时，我以顺序的方式（按顺序意义，n+1）得到数字的组合。因此，期望的输出是：

ResultA = [[0],[2],[5],[6],[5,6]]
ResultB = [[5],[6],[8],[9],[5,6],[8,9]]
ResultC = [[6],[7],[8],[9],[6,7],[7,8],[8,9],[6,7,8],[7,8,9],[6,7,8,9]]

下面是我尝试过的：

sorted_ids = sorted(number_collection)
combinations = [sorted_ids[j: j + i] for i in range(1, len(sorted_ids)) for j in range(len(sorted_ids) - i + 1)]

问题是它对数组C有效，但对其他数组没有那么好的效果。你知道吗

---

问题2problem 1的结果是这个问题的输入。问题是我想要的组合，存在于数字的唯一元素上。（我不确定我是否能用语言恰当地解释），下面是期望的输出：

FinalResultA = [[0],[2],[5,6]]
FinalResultB = [[5,6],[8,9]]
FinalResultC = [[6,7,8,9]]

有什么方法（以性能为导向）对我有用吗？你知道吗

Answer 1

这是一个相当有效的方法，虽然它需要O（N）辅助空间，但如果运行次数很小，则不应该很重要：

from itertools import groupby

def ngrams(seq):
    stop = len(seq)+1
    for n in range(2, stop):
        for i in range(stop - n):
            yield seq[i:i+n]

def get_combos(seq):
    runs = []
    for _, g in groupby(enumerate(seq), lambda x:x[1]-x[0]):
        run = [a for _, a in g]
        for x in run:
            yield [x]
        if len(run) > 1:
            runs.append(run)
    for run in reversed(runs):
        yield from ngrams(run)

注意，这使用this classic approach对连续整数进行分组。它在连续整数组上迭代，“runs”，并生成作为单个元素列表的任何单个整数。如果运行长度超过1，我会将其添加到运行列表中。最后，以相反的方式迭代运行列表，得到“n-grams”，从order2到orderlen（run）。你知道吗

行动中：

>>> A = [0,2,5,6]
>>> B = [5,6,8,9]
>>> C = [6,7,8,9]
>>> list(get_combos(A))
[[0], [2], [5], [6], [5, 6]]
>>> list(get_combos(B))
[[5], [6], [8], [9], [8, 9], [5, 6]]
>>> list(get_combos(C))
[[6], [7], [8], [9], [6, 7], [7, 8], [8, 9], [6, 7, 8], [7, 8, 9], [6, 7, 8, 9]]

注意get_combos假设输入是排序的。

编辑

但是，对于：

>>> D = [6,7,9,12,13,14,20,21,30]

这将产生：

>>> list(get_combos(D))
[[6], [7], [9], [12], [13], [14], [20], [21], [30], [20, 21], [12, 13], [13, 14], [12, 13, 14], [6, 7]]

也就是说，3序列在产生后续运行的2序列之前开始。如果要在n+1 len序列之前生成所有n-len序列，请使用以下方法：

from itertools import groupby

def ngrams(seq, max_len):
    curr = seq
    for n in range(1, max_len + 1):
        nxt = []
        for run in curr:
            run_len = len(run)
            if run_len > n:
                nxt.append(run)
            for i in range(run_len + 1 - n):
                yield run[i:i+n]
        curr = nxt

def _sub_index(t):
    return t[1] - t[0]

def get_consecutive_runs(seq):
    grouped = groupby(enumerate(seq), _sub_index)
    for _, g in grouped:
        yield [a for _, a in g]


def get_combos(seq):
    runs = list(get_consecutive_runs(seq))
    max_len = max(map(len, runs))
    yield from ngrams(runs, max_len)

结果如下：

>>> list(get_combos(D))
[[6], [7], [9], [12], [13], [14], [20], [21], [30], [6, 7], [12, 13], [13, 14], [20, 21], [12, 13, 14]]

Answer 2

以下是一个函数中的两种解决方案，无需任何外部库：

A = [0,2,5,6]
B = [5,6,8,9]
C= [6,7,8,9]

def finding_sequence(list_1):
    sub_list = []
    for j, i in enumerate(list_1):

        try:
            if list_1[j] - list_1[j - 1] == 1:
                sub_list.append((list_1[j - 1], list_1[j]))
            else:
                sub_list.append('_pos')


        except IndexError:

            pass

    sub_final_result = []
    check_result=[]
    if '_pos' not in sub_list[1:]:
        for i in sub_list[1:]:
            for k in i:
                if k not in sub_final_result:
                    sub_final_result.append(k)
                    check_result.append(k)

    else:
        for i in sub_list:
            if i != '_pos':
                sub_final_result.append(i)
                for i1 in i:
                    check_result.append(i1)


    for i1 in list_1:
        if i1 not in check_result:
            sub_final_result.append([i1])

    return sub_final_result

测试用例：

print(finding_sequence(A))

输出：

[(5, 6), [0], [2]]

第二

print(finding_sequence(B))

输出：

[(5, 6), (8, 9)]

附言：一个要求是：如果我的答案对你有帮助，不要接受，就用它吧。你知道吗