Задача:
Нужно получить 9000 рядов шириной 6 элементов, которые отличаются друг от друга минимум на 4 элемента.
Например: есть массив из размещений с повторениями трех элементов (0, 1 и 2)
Из них получается 3^6 = 729 рядов отличающихся на 1 элемент минимум.
Что пробовали: Исходя из программы:
from itertools import *
import pandas as pd
'''переменные
n - счетчик отличий листов друг от друга
b - рандомный индекс в функции diff
d - словарь размещений с повторениями
dicttr - отсортированный словарь размещений с повторениями
num_diff - количество элементов, на которые отличаются два листа
count - кол-во листов, которое должно быть в целевом словаре
dicttc - целевой словарь (словарь, где все листы отличаются друг от друга минимум на 3 элемента)'''
# фунция сравнения двух листов, с 6 элементами каждый - считает кол-во отличий
def diff(lst0, lst1): # lst0 - лист сравнения 0, lst1 - лист сравнения 1
n = 0 # счетчик отличий
b = 0 # просто индекс, меняющийся от 0 до 5 (на все 6 знаков листа)
while b <= 5:
if lst0[b] != lst1[b]:
b = b + 1
n = n + 1
else:
n = n
b = b + 1
return n
# создаем словарь размещений с повторениями
d_index = 0
d = {}
for i in product('012', repeat=6):
d[d_index] = i
d_index = d_index + 1
# преобразуем словарь в dataframe (столбцы - индексы, строки - варианты размещений с повторениями)
df = pd.DataFrame.from_dict(d, orient='index')
df = df.astype(int) # задаем все значения в таблице как числа (были строками)
df['Total'] = df.sum(axis=1) # добавляем итоговые значения суммы по строке (суммируем строку)
# сортируем столбец Total по возрастанию -> меняем индексацию -> удаляем столбец с индексами
df = df.sort_values(by=['Total']).reset_index().drop('index', 1)
# print(df.head(15))
# для дальнейшей работы сносим столбец Total
df = df.drop('Total', 1)
# print(df.head(15))
# преобразуем df обратно в словарь
dicttr = df.T.to_dict('list')
num_diff = 0 # кол-во отличий среди листов
dicttc = {0: [0, 0, 0, 0, 0, 0]}
count = 9000
for dicttr_index in range(len(dicttr)):
for dicttc_index in range(len(dicttc)):
while len(dicttc) < count:
if diff(dicttr[dicttr_index], dicttc[dicttc_index]) >= 4:
num_diff = num_diff + 1
if num_diff == len(dicttc):
dicttc[len(dicttc)] = dicttr[dicttr_index]
num_diff = 0
del dicttr[dicttr_index]
Вывод, если только два элемента (0 и 1): {0: [0, 0, 0, 0, 0, 0], 1: [1, 1, 0, 0, 1, 1], 2: [1, 1, 1, 1, 0, 0], 3: [0, 0, 1, 1, 1, 1]}
При 2 элементах получается 4 ряда, соответствующих требованиям, при 3 (0, 1 и 2) получается 11, мне нужно 9000.
Задача получается отлично, но если нарастить количество элементов, чтобы достигнуть массива в 9000 листов - код работает оочень долго.
Статистическое решение в комбинаторике не найдено, а для регрессии VAR слишком мало данных.
Возможно ли решение такой задачи статистически? Какой раздел математики может помочь? Или как можно оптимизировать задачу?