Комбинации М элементов из N с непоследовательными повторениями - PullRequest
Новая
       17

Комбинации М элементов из N с непоследовательными повторениями

0 голосов
/ 20 февраля 2019

У меня есть следующая проблема, которую можно суммировать следующим образом:

Представьте, что у вас есть два целых числа больше 0, N (который определяет массив n=np.array(range(N)) и M. Мы хотели быгенерировать все возможные комбинации элементов из n длиной M с условием, что нет равных элементовявляются последовательными .

Например, для N = 3 (n=[0,1,2]) и M = 3 мы должны получить: 

(0,1,0), (0,1,2) (0,2,0), (0,2,1), (1,0,1), (1,0,2), (1,2,0), (1,2,1), (2,0,1), (2,0,2), (2,1,0), (2,1,2)

То есть такие комбинации, как(0,0,1), (1,1,1), (2,1,1) ... и т. Д., Не должны появляться.Обратите внимание, что число всех допустимых комбинаций просто дается N*(N-1)**(M-1).

На данный момент для такого примера я использую этот простой скрипт (который также вычисляет все комбинации различной длины от m = 1 до m = M): 

import numpy as np
N = 3
M = 3
p = np.array(range(N))  

ic = [0]*M
c2 = np.zeros((int(N*(N-1)**(M-1)),M))
c1 = np.zeros((int(N*(N-1)**(M-2)),M-1))
c0 = np.zeros((int(N*(N-1)**(M-3)),M-2))
for i in p:
    c0[ic[0],:] = [i]
    ic[0] += 1
    for j in p[p!=i]:
        c1[ic[1],:] = [i,j]
        ic[1] += 1
        for k in p[p!=j]:
            c2[ic[2],:] = [i,j,k]
            ic[2] += 1

Проблемаявляется то, что это работает только для этого конкретного случая с M = 3, и M может быть любым целым числом больше 0. Поэтому для некоторого M предыдущий код должен иметь M вложенных циклов, которые должны были бы быть введены вручную.

Я пытался определить рекурсивную функцию с переменным числом циклов, как эта, которая вычисляет число комбинаций (число, указанное в уравнении выше): 

def rec_f(c,N,M):   
    if n>=1:
        for x in range(N):             
            c=rec_f(c,N,M-1)
    else:
        c += 1            
    return c

, который я даже не знаю, почему это работает для этой простой проблемы.Дело в том, что мне нужно знать индексы предыдущих циклов, чтобы иметь возможность копировать сценарий, который генерирует все возможные комбинации, и я не знаю, как это сделать.

Я также пытался создать один уникальный цикл for (который будет повторяться N * (N-1) ^ (M-1) раз), имея в виду, что комбинации могут быть выражены в виде чиселв базе N, но, поиграв некоторое время, я не получил ничего полезного.

Буду признателен за любую помощь, заранее спасибо (и извините за длинный пост)!

Ответы [ 2 ]

0 голосов
/ 20 февраля 2019

То, что вы описываете, достижимо с помощью (мощной) библиотеки Python itertools, а затем отфильтровывает ее в зависимости от вашего состояния.Но то, что вы хотите, это скорее product , а не комбинация массива.

Вот один из способов сделать это, предполагая аргументы N и M. 

import numpy as np
import itertools

p = np.arange(N)

Получите произведения длины 3: 

product_iterator = itertools.product(p, repeat=M)

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

product_list = np.array(list(product_iterator))

В этот момент вы получили массив всех 27 комбинаций:[[0 0 0], [0 0 1], [0 0 2], ..., [2 2 1], [2 2 2]].Теперь вы можете отфильтровать их по желаемым критериям.

В вашем случае, «отсутствие повторяющихся элементов подряд» означает проверку того, что разность между двумя последовательными элементами никогда не равна нулю.Таким образом, мы получаем различия: 

diffs = np.diff(product_list,axis=1)

Это дает: 

[[ 0  0]
 [ 0  1]
 [ 0  2]
 [ 1 -1]
 [ 1  0]
 [ 1  1]
 [ 2 -2]
 [ 2 -1]
 [ 2  0]
 [-1  0]
 [-1  1]
 [-1  2]
 [ 0 -1]
 [ 0  0]
 [ 0  1]
 [ 1 -2]
 [ 1 -1]
 [ 1  0]
 [-2  0]
 [-2  1]
 [-2  2]
 [-1 -1]
 [-1  0]
 [-1  1]
 [ 0 -2]
 [ 0 -1]
 [ 0  0]]

И теперь мы проверяем, строка за строкой, есть ли нули: 

no_consec_indexes = np.apply_along_axis(lambda x: np.all(x), 1, diffs)

Это дает массив логических значений no_consec_indexes: 

array([False, False, False,  True, False,  True,  True,  True, False,
       False,  True,  True, False, False, False,  True,  True, False,
       False,  True,  True,  True, False,  True, False, False, False])

Вы можете использовать его для фильтрации исходного массива продуктов: 

product_list[no_consec_indexes]

Что дает желаемый ответ: 

 array([[0, 1, 0],
       [0, 1, 2],
       [0, 2, 0],
       [0, 2, 1],
       [1, 0, 1],
       [1, 0, 2],
       [1, 2, 0],
       [1, 2, 1],
       [2, 0, 1],
       [2, 0, 2],
       [2, 1, 0],
       [2, 1, 2]])
0 голосов
/ 20 февраля 2019

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

def combinations(elements, m, last=-1):
    if m:
        for x in elements:
            if x != last:
                for rest in combinations(elements, m-1, x):
                    yield (x,) + rest
    else:
        yield ()

Или немного более компактно, с yield from выражение генератора: 

def combinations(elements, m, last=-1):
    if m:
        yield from ((x,) + rest for x in elements if x != last
                                for rest in combinations(elements, m-1, x))
    else:
        yield ()

Пример результатов для обеих версий: 

print(*combinations(range(3), 3))
# (0, 1, 0), (0, 1, 2), (0, 2, 0), (0, 2, 1), (1, 0, 1), (1, 0, 2), (1, 2, 0), (1, 2, 1), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 2)
...