Как проверить, существует ли в наборе «несортированная версия» списка?

Question

Я хочу создать список списков. Каждый подсписок будет создан путем выборки из range(100). Мне нужно убедиться, что списки, которые идентичны (т.е. имеют одинаковые элементы), но имеют различную сортировку, не существуют в главном списке (т.е. я не хочу, чтобы [1,2,3] и [2,1,3] в главном списке одновременно) , Вот что я написал:

import random as rd
my_list = []
while len(my_list) < 50:
    p = rd.sample(range(100), 10)
    if p not in my_list: my_list.append(p)

Проблема в том, что if p not in my_list не выполняет работу, поскольку не считает [1,2,3] и [2,1,3] идентичными. Я думал сделать что-то вроде этого:

my_list = []
while len(my_list) < 50:
    p = rd.sample(range(100), 10)
    for i in range(len(my_list)):
        if set(p) != set(my_list[i]): my_list.append(p)

Но, похоже, это застревает в первом цикле, и программа никогда не заканчивается. Мне было интересно, если есть простой способ сделать это в Python?

Answer 1

Вы добавляете сгенерированный список в (, если условно из) для цикла.
Но , учитывая тот факт, что my_list в начале пуст:

• Цикл для представляет собой без операции
• , если никогда не выполняется
• Таким образом, ни один элемент не добавляется к my_list , поэтому он никогда не изменяется
• Вы получаете бесконечный цикл (или вы в тупиковой ситуации)

Чтобы исправить это, немного измените рефакторинг вашего цикла ( [Python 3.Docs]: составные операторы - оператор for ) в:

for existing in my_list:
    if set(p) == set(existing):
        break
else:
    my_list.append(p)

Запускается менее чем за 0.1 секунд.

Чтобы еще больше улучшить вещи, храните наборы в отдельном списке (чтобы избежать ненужного пересчета их слишком много раз, чем необходимо) и используйте его для проверки включения:

code.py

#!/usr/bin/env python3

import sys
import random
import time


def main():
    final_list = list()
    sentinel_list = list()
    start_time = time.time()
    count = 0
    while len(sentinel_list) < 50:
        inner_list = random.sample(range(100), 10)
        inner_set = set(inner_list)
        if inner_set not in sentinel_list:
            final_list.append(inner_list)
            sentinel_list.append(inner_set)
        count += 1
    del sentinel_list
    print("{:d} element list generated in {:d} iterations".format(len(final_list), count))
    print("Took {:.3f} seconds".format(time.time() - start_time))


if __name__ == "__main__":
    print("Python {:s} on {:s}\n".format(sys.version, sys.platform))
    main()
    print("\nDone.")

выход

[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q056317300]> "e:\Work\Dev\VEnvs\py_064_03.07.03_test0\Scripts\python.exe" code.py
Python 3.7.3 (v3.7.3:ef4ec6ed12, Mar 25 2019, 22:22:05) [MSC v.1916 64 bit (AMD64)] on win32

50 element list generated in 50 iterations
Took 0.003 seconds

Done.

Answer 2

Другие ответы, по-видимому, пропустили неквадратичное решение по сохранению набора морозилок:

def unique_without_order_retaining_order(L):
    output = []
    seen = set()
    for item in L:
        f = frozenset(item)
        if f not in seen:
           seen.add(f)
           output.append(item)
    return output

Это можно адаптировать к генератору.

Answer 3

Ваша логика не совсем верна - вы хотите добавить что-то в список, только когда его еще нет. Вот как это сделать, используя параметр option else цикла for, который будет выполняться только в том случае, если break никогда не выполняется. Как это работает, описано в документе оператора for.

my_list = []
for p in [1,2,3], [3,2,1], [4,5,6]:
    for c in my_list:
        if set(p) == set(c):
            break
    else:
        my_list.append(p)

print(my_list)  # -> [[1, 2, 3], [4, 5, 6]]

Также неэффективно преобразовывать каждую комбинацию в set более одного раза, поэтому вы можете вывести эту часть из цикла:

my_list = []
for p in [1,2,3], [3,2,1], [4,5,6]:
    set_p = set(p)  # do this here
    for c in my_list:
        if set_p == set(c):
            break
    else:
        my_list.append(p)