按具有重復項的另一個串列對串列進行排序

我有兩個串列 [1, 2, 3, 1, 2, 1] 和 [a, b, c, d, e, f]。我想根據對第一個串列進行排序的排列對第二個串列中的元素重新排序。對第一個串列進行排序得到 [1, 1, 1, 2, 2, 3] 但是第二個串列有許多可能的排列按第一個排序，即 [a, d, f, b, e, c], [ d、f、a、e、b、c] 等。

如何在 python 中以有效的方式生成所有這些排列？

如果我只想要一個排列，我可以通過這樣的方式得到一個：

sorted_numbers, sorted_letters = list(zip(*[(x, y) for x, y in sorted(zip(numbers, letters))]))

uj5u.com熱心網友回復：

如果串列的大小不是太大，您可以使用串列理解來通過輔助函式過濾所有排列：

from itertools import permutations


def is_valid_ordering(perm: str, ch_to_order: dict) -> bool:
    if not perm or len(perm) <= 1:
        return True
    for ch1, ch2 in zip(perm[:-1], perm[1:]):
        if ch_to_order[ch1] > ch_to_order[ch2]:
            return False
    return True


lst_1 = [1, 2, 3, 1, 2, 1]
lst_2 = ['a', 'b', 'c', 'd', 'e', 'f']
ch_to_order = {ch: o for ch, o in zip(lst_2, lst_1)}
valid_permutations = [
    list(p) for p in permutations(lst_2)
    if is_valid_ordering(p, ch_to_order)
]
for valid_perm in valid_permutations:
    print(valid_perm)

輸出：

['a', 'd', 'f', 'b', 'e', 'c']
['a', 'd', 'f', 'e', 'b', 'c']
['a', 'f', 'd', 'b', 'e', 'c']
['a', 'f', 'd', 'e', 'b', 'c']
['d', 'a', 'f', 'b', 'e', 'c']
['d', 'a', 'f', 'e', 'b', 'c']
['d', 'f', 'a', 'b', 'e', 'c']
['d', 'f', 'a', 'e', 'b', 'c']
['f', 'a', 'd', 'b', 'e', 'c']
['f', 'a', 'd', 'e', 'b', 'c']
['f', 'd', 'a', 'b', 'e', 'c']
['f', 'd', 'a', 'e', 'b', 'c']

或者，如果串列很大并且因此效率很重要，您可以只構建有效的排序（請參閱Stef 的答案以獲得比下面更好的方法）：

from collections import defaultdict
from itertools import permutations, product
from iteration_utilities import flatten

lst_1 = [1, 2, 3, 1, 2, 1]
lst_2 = ['a', 'b', 'c', 'd', 'e', 'f']
equivalent_chars = defaultdict(list)
for o, ch in zip(lst_1, lst_2):
    equivalent_chars[o].append(ch)
equivalent_char_groups = [g for o, g in sorted(equivalent_chars.items())]
all_group_permutations = [[list(p) for p in permutations(group)]
                          for group in equivalent_char_groups]
valid_permutations = [
    list(flatten(p)) for p in product(*all_group_permutations)
]
for valid_perm in valid_permutations:
    print(valid_perm)

uj5u.com熱心網友回復：

使用itertools建排列每個重復鍵的笛卡爾乘積：

代碼

from itertools import chain, permutations, groupby, product
from operator import itemgetter

def all_sorts(numbers, letters):
    return [list(map(itemgetter(1), chain.from_iterable(p))) for p in product(*(permutations(g) for _,g in groupby(sorted(zip(numbers, letters)), key=itemgetter(0))))]

print( all_sorts([1,2,3,1,2,1], 'abcdef') )
# [['a', 'd', 'f', 'b', 'e', 'c'], ['a', 'd', 'f', 'e', 'b', 'c'], ['a', 'f', 'd', 'b', 'e', 'c'], ['a', 'f', 'd', 'e', 'b', 'c'], ['d', 'a', 'f', 'b', 'e', 'c'], ['d', 'a', 'f', 'e', 'b', 'c'], ['d', 'f', 'a', 'b', 'e', 'c'], ['d', 'f', 'a', 'e', 'b', 'c'], ['f', 'a', 'd', 'b', 'e', 'c'], ['f', 'a', 'd', 'e', 'b', 'c'], ['f', 'd', 'a', 'b', 'e', 'c'], ['f', 'd', 'a', 'e', 'b', 'c']]

這種方法是最佳的，因為它直接生成解決方案，而不是從龐大的候選串列中過濾它們。對于給定的大小為 6 的示例串列，它僅生成 12 個解決方案，而不是過濾大小為 6 的串列的所有 720 個排列。

這個怎么運作：

首先，我們使用sorted和按鍵進行排序和分組itertools.groupby。注意operator.itemgetter(0)與lambda t: t[0].

>>> [list(g) for _,g in groupby(sorted(zip(numbers, letters)), key=itemgetter(0))]
[[(1, 'a'), (1, 'd'), (1, 'f')],
 [(2, 'b'), (2, 'e')],
 [(3, 'c')]]

然后我們生成每個鍵的可能排列，itertools.permutation在每個組上使用。

>>> [list(permutations(g)) for _,g in groupby(sorted(zip(numbers, letters)), key=itemgetter(0))]
[[((1, 'a'), (1, 'd'), (1, 'f')), ((1, 'a'), (1, 'f'), (1, 'd')), ((1, 'd'), (1, 'a'), (1, 'f')), ((1, 'd'), (1, 'f'), (1, 'a')), ((1, 'f'), (1, 'a'), (1, 'd')), ((1, 'f'), (1, 'd'), (1, 'a'))],
 [((2, 'b'), (2, 'e')), ((2, 'e'), (2, 'b'))],
 [((3, 'c'),)]]

然后我們構建這些排列串列的笛卡爾積，使用itertools.product; 我們從笛卡爾積中的每個元組重建一個串列，使用itertools.chain連接。最后，我們“取消裝飾”，丟棄鍵并只保留字母，我map(itemgetter(1), ...)已經這樣做了，但可以等效地使用串列理解來完成[t[1] for t in ...]。

>>> [list(map(itemgetter(1), chain.from_iterable(p))) for p in product(*(permutations(g) for _,g in groupby(sorted(zip(numbers, letters)), key=itemgetter(0))))]
[['a', 'd', 'f', 'b', 'e', 'c'], ['a', 'd', 'f', 'e', 'b', 'c'], ['a', 'f', 'd', 'b', 'e', 'c'], ['a', 'f', 'd', 'e', 'b', 'c'], ['d', 'a', 'f', 'b', 'e', 'c'], ['d', 'a', 'f', 'e', 'b', 'c'], ['d', 'f', 'a', 'b', 'e', 'c'], ['d', 'f', 'a', 'e', 'b', 'c'], ['f', 'a', 'd', 'b', 'e', 'c'], ['f', 'a', 'd', 'e', 'b', 'c'], ['f', 'd', 'a', 'b', 'e', 'c'], ['f', 'd', 'a', 'e', 'b', 'c']]

uj5u.com熱心網友回復：

另一個沒有過濾的實作：

from itertools import product, permutations, chain

numbers = [1, 2, 3, 1, 2, 1]
letters = ['a', 'b', 'c', 'd', 'e', 'f']

grouper = {}
for number, letter in zip(numbers, letters):
    grouper.setdefault(number, []).append(letter)
groups = [grouper[number] for number in sorted(grouper)]
for prod in product(*map(permutations, groups)):
    print(list(chain.from_iterable(prod)))

輸出：

['a', 'd', 'f', 'b', 'e', 'c']
['a', 'd', 'f', 'e', 'b', 'c']
['a', 'f', 'd', 'b', 'e', 'c']
['a', 'f', 'd', 'e', 'b', 'c']
['d', 'a', 'f', 'b', 'e', 'c']
['d', 'a', 'f', 'e', 'b', 'c']
['d', 'f', 'a', 'b', 'e', 'c']
['d', 'f', 'a', 'e', 'b', 'c']
['f', 'a', 'd', 'b', 'e', 'c']
['f', 'a', 'd', 'e', 'b', 'c']
['f', 'd', 'a', 'b', 'e', 'c']
['f', 'd', 'a', 'e', 'b', 'c']

它首先使用 dict 將字母按數字分組：

grouper = {1: ['a', 'd', 'f'], 2: ['b', 'e'], 3: ['c']}

然后它對數字進行排序并提取它們的字母組：

groups = [['a', 'd', 'f'], ['b', 'e'], ['c']]

然后只需置換每個組并構建和鏈接產品。

標籤：蟒蛇-3.x 排序

上一篇：繪制決策樹

下一篇：如何按鍵值對嵌入的字典串列進行排序？