#python #pandas #itertools
#python #pandas #python-itertools
Вопрос:
Проблема: У меня есть таблица, из которой мне нужно извлечь все допустимые комбинации строк (или столбцов, если я транспонирую таблицу). столбцы имеют значения только » » или «-«, и комбинация считается допустимой, когда хотя бы в одной из строк комбинации есть » «, то есть любая комбинация с «-» во всех строках недопустима.
Пример таблицы:
Guns P_01 P_02 P_03 P_04 P_05 P_06 P_07
0 G_01 - -
1 G_02 - -
2 G_03 - - -
3 G_04 - - - -
4 G_05 - - - -
5 G_06 - - -
6 G_07 - - - -
Пример допустимой комбинации:
0 G_01 - -
1 G_02 - -
Пример недопустимой комбинации:
3 G_04 - - - -
4 G_05 - - - -
Чтобы получить все комбинации, я пытаюсь использовать комбинацию itertools и помещаю результат в список:
dfcomb = []
dfcomb = df.apply(lambda r: list(combinations(r, 2)), axis=0)
Вывод:
Guns P_01 P_02 P_03 P_04 P_05 P_06 P_07
0 (G_01, G_02) ( , ) (-, ) ( , ) ( , -) ( , ) (-, ) ( , -)
1 (G_01, G_03) ( , -) (-, -) ( , -) ( , ) ( , ) (-, ) ( , )
2 (G_01, G_04) ( , ) (-, ) ( , ) ( , -) ( , -) (-, -) ( , -)
3 (G_01, G_05) ( , ) (-, ) ( , ) ( , -) ( , -) (-, -) ( , -)
4 (G_01, G_06) ( , -) (-, -) ( , -) ( , ) ( , ) (-, ) ( , )
5 (G_01, G_07) ( , ) (-, ) ( , ) ( , -) ( , -) (-, -) ( , -)
6 (G_02, G_03) ( , -) ( , -) ( , -) (-, ) ( , ) ( , ) (-, )
7 (G_02, G_04) ( , ) ( , ) ( , ) (-, -) ( , -) ( , -) (-, -)
8 (G_02, G_05) ( , ) ( , ) ( , ) (-, -) ( , -) ( , -) (-, -)
9 (G_02, G_06) ( , -) ( , -) ( , -) (-, ) ( , ) ( , ) (-, )
10 (G_02, G_07) ( , ) ( , ) ( , ) (-, -) ( , -) ( , -) (-, -)
11 (G_03, G_04) (-, ) (-, ) (-, ) ( , -) ( , -) ( , -) ( , -)
12 (G_03, G_05) (-, ) (-, ) (-, ) ( , -) ( , -) ( , -) ( , -)
13 (G_03, G_06) (-, -) (-, -) (-, -) ( , ) ( , ) ( , ) ( , )
14 (G_03, G_07) (-, ) (-, ) (-, ) ( , -) ( , -) ( , -) ( , -)
15 (G_04, G_05) ( , ) ( , ) ( , ) (-, -) (-, -) (-, -) (-, -)
16 (G_04, G_06) ( , -) ( , -) ( , -) (-, ) (-, ) (-, ) (-, )
17 (G_04, G_07) ( , ) ( , ) ( , ) (-, -) (-, -) (-, -) (-, -)
18 (G_05, G_06) ( , -) ( , -) ( , -) (-, ) (-, ) (-, ) (-, )
19 (G_05, G_07) ( , ) ( , ) ( , ) (-, -) (-, -) (-, -) (-, -)
20 (G_06, G_07) (-, ) (-, ) (-, ) ( , -) ( , -) ( , -) ( , -)
Но теперь я застрял, я знаю, что я должен использовать цикл, чтобы проверить, допустима ли какая-либо комбинация или нет, но как я могу это сделать?
Комментарии:
1. Я запутался в вашем описании. Для вашего ожидаемого результата похоже, что комбинация допустима, если в ней есть
и-, а неили--. Можете ли вы пояснить это?2. Допустимой комбинацией является » » или » -«. Недопустимой комбинацией является только «—«, если в каком-либо из столбцов присутствует «—» — недопустимая комбинация строк
Ответ №1:
Если вы считаете и — истиной и False и применяете or операцию для каждого столбца:
G_01 - -
G_02 - -
---------------------------------------
OR ==> All true. This combo is valid
G_04 - - - -
G_05 - - - -
---------------------------------------
OR - - - - ==> Not all true. This combo is invalid
Единственная оставшаяся проблема заключается в том, как их быстро сравнить. Для этого мы можем использовать функцию трансляции массива numpy. Вкратце, трансляция массива — это процесс выполнения операций над массивами разных размеров:
# When you compare an array to a scalar, the logical action is to compare
# every element of the array that scalar
[a, b, c] > d is equivalent to [a > d, b > d, c > d]
# If you want to compare every element of a list against every element of
# another list, things get a little tricky
[a, b, c] > [d, e] ???
# The trick is to raise the raise the second array up another dimension so you
# you can a comparison matrix. The first array remains 1D, the second array is
# now 2D
[a, b, c] > [[d], [e]]
# One way to visualize it
d e
a a > d a > e
b b > d b > e
c c > d c > e
Вот ответ на ваш вопрос:
# Life is a lot easier if you put Guns on the index
df.set_index('Guns', inplace=True)
# A 2D array of True/False
a = df.applymap(lambda x: x == ' ').to_numpy()
# A 3D array to be used for in the OR operation
b = a[:, None]
# OR-ing every gun with every other gun
c = np.all(a | b, axis=-1)
# This is what c looks like, with some labels added
# G_01 G_02 G_03 G_04 G_05 G_06 G_07
# |------------------------------------------------
# G_01 | False True False False False False False ==> (G_01, G_02) is valid
# G_02 | True False True False False True False ==> (G_02, G_01), (G_02, G_03) and (G_02, G_06) are valid
# G_03 | False True False True True False True
# G_04 | False False True False False True False
# G_05 | False False True False False True False
# G_06 | False True False True True False True
# G_07 | False False True False False True False
# Obviously (G_01, G_02) and (G_02, G_01) are the same combo so we don't need
# to collect both of them. We only need to work with the upper triangle in the
# matrix (`triu` means triangle upper)
valid_combinations = [(df.index[i], df.index[j]) for i,j in np.dstack(np.triu_indices_from(c))[0] if c[i][j]]
Поскольку он использует широковещательную передачу numpy, он извлекает выгоду из всей базовой векторизации. Я запустил фрейм данных размером 1000 x 1000 (1 МЛН элементов) менее чем за 3 секунды.
Редактировать: чтобы расширить это, чтобы охватить комбинации произвольного размера, вы просто продолжаете увеличивать матрицу сравнения с каждой итерацией:
def get_valid_combos(df, combo_size=2):
assert combo_size >= 2, 'combo_size must be at least 2'
a = df.applymap(lambda x: x == ' ').to_numpy()
result = a
while combo_size > 1:
a = a[:, None]
result = result | a
combo_size -= 1
result = result.all(axis=-1)
# Return True if array is monotonically increasing to avoid duplicates
# like (G_1, G_2, G_3) and (G_1, G_3, G_2)
is_increasing = lambda arr: (np.diff(arr) > 0).all()
valid_indicies = np.array(result.nonzero()).transpose()
return [tuple(df.index[idx]) for idx in valid_indicies if is_increasing(idx)]
Обратите внимание, что это число растет экспоненциально. Если у вас есть n оружие, для этого требуется n ^ combo_size пространство и, вероятно n ^ (2 * combo_size) , время. Есть возможности для оптимизации: если G_1 и G_2 составляют допустимую комбинацию, все, что связано с этими двумя, также допустимо и, следовательно, экономит нам некоторое время. Но сейчас я слишком ленив.
Комментарии:
1. большое вам спасибо! Это работает лучше, чем я думаю, но как это работает для комбинации из 3 или более элементов? например, если ни одна комбинация из 2 элементов не дает допустимой комбинации, мне нужно протестировать с 3 комбинациями или более.
Ответ №2:
Вы можете использовать a for-loop для перебора всех сгенерированных вами комбинаций и проверки их с помощью if-statement . any Можно проверить, есть ли столбцы, в которых оба из них имели - символ. Как только вы выяснили, является ли комбинация допустимой, вы можете добавить ее в список допустимых комбинаций.
valid_combinations = []
for combination in combinations:
if not any(p[0] == "-" and p[1] == "-" for p in combination):
valid_combinations.append(combination)
Это можно упростить, используя представление списка:
valid_combinations = [combination for combination in combinations if not any(p[0] == "-" and p[1] == "-" for p in combination)]