Как вычислить отклонение (перестановку) списка с повторяющимися элементами - PullRequest
Новая
       40

Как вычислить отклонение (перестановку) списка с повторяющимися элементами

0 голосов
/ 17 октября 2018

У меня есть список с повторяющимися элементами, то есть orig = [1,1,1,2,2,3].
Я хочу создать расстройство b = f(orig), чтобы для каждого местоположения значение в b отличалось от значения в orig: 

b[i] != orig[i], for all i

Я знаю решение, когда все элементы в orig уникальны, но это более сложный случай.

Разработка решения на python, но любой язык подойдет.

Ответы [ 2 ]

0 голосов
/ 17 октября 2018

Если ваш список содержит значительную часть дубликатов, может быть сложно быстро найти отклонение от нормы.

В этом случае вы можете попробовать подход на основе графа.

Обработать исходный список, чтобы получить график,каждый элемент связан с неравными элементами (легко для отсортированного списка).

Затем создайте идеальное совпадение (если число элементов четное) или почти идеальное совпадение (для нечетного числа здесь вам нужно найти подходящую пару и присоединить к ней один узел).

Края совпадения указывают на обмены, которые могут привести к расстройству.

Библиотека Python networkx должна содержать необходимые методы.

0 голосов
/ 17 октября 2018

Очевидно, что не очень эффективное решение 

import itertools
set([s for s in itertools.permutations(orig) if not any([a == b for a, b in zip(s, orig)])])

Второй метод и первое улучшение - это this perm_unique: 

 [s for s in perm_unique(orig) if not any([a == b for a, b in zip(s, orig)])]

Третийметод состоит в том, чтобы использовать этот супер быстрый unique_permutations алгоритм .

 import copy
 [copy.copy(s) for s in unique_permutations(orig) if not any([a == b for a, b in zip(s, orig)])]

В моей записной книжке с %%timeit начальный метод занимает 841 µs, и мы улучшаемся до 266 µs, а затем до 137 µs.

Редактировать

Не могу не задумываться, сделал небольшое редактирование второго метода.Не было времени погрузиться в последний метод.Для объяснения, сначала посмотрите оригинальный пост (ссылка выше).Тогда я только добавил чек and el != elements[depth], который заставляет состояние расстройства.С этим мы получаем время работы 50 µs. 

from collections import Counter

def derangement_unique(elements):
    list_unique = Counter(elements)
    length_list = len(elements)  # will become depth in the next function
    placeholder = [0]*length_list  # will contain the result
    return derangement_unique_helper(elements, list_unique, placeholder, length_list-1)

def derangement_unique_helper(elements, list_unique, result_list, depth):
    if depth < 0:   # arrived at a solution
        yield tuple(result_list)
    else:
        # consider all elements and how many times they should still occur 
        for el, count in list_unique.items():
            # ... still required and not breaking the derangement requirement
            if count > 0 and el != elements[depth]:   
                result_list[depth] = el  # assignment element
                list_unique[el] -= 1   # substract number needed
                # loop for all possible continuations 
                for g in derangement_unique_helper(elements, list_unique, result_list, depth-1):
                    yield g
                list_unique[el] += 1


list(derangement_unique(orig))
...