5

Задача:
Нужно получить 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 слишком мало данных.

Возможно ли решение такой задачи статистически? Какой раздел математики может помочь? Или как можно оптимизировать задачу?

2

2 ответа 2

5

такой код работает побыстрее, но тоже до 9000 еще долго доходить будет, учитывая, что сложность алгоритма растет как O(n^2), а рост кол-ва вариантов не такой бодрый:

введите сюда описание изображения

from itertools import *

# сформировать
for size in range(2, 100):
    objects = product(range(size), repeat=6)

    selected = []

    for obj_created in objects:
        for obj_selected in selected[::-1]:
            if sum(obj_selected[i] != obj_created[i] for i in range(6)) < 4:
                break
        else:
            selected.append(obj_created)

    print(size, len(selected))

Второй вариант алгоритма:

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

# перебрать разные размеры комбинаций (сколько разных чисел формируют комбинацию)
for size in range(2, 100):

    selected = []

    # перебрать все варианты
    for value in range(0, size**6):

        # вычислить цифры, составляющие вариант
        tmp = value
        data = []
        for i in range(6):
            digit = tmp % size
            tmp //= size

            data.append(digit)

        # проверить, удовлетворяет ли вариант критериям отбора
        for obj_selected in selected[::-1]:
            if sum(obj_selected[i] != data[i] for i in range(6)) < 4:
                break
        else:
            selected.append(data)

    # вывести результат поиска
    print(size, len(selected))

P.S.

код на C++, который и позволил решить задачу за 2,5 часа:

#include <conio.h>

#include <iostream>

#include <mutex>
#include <thread>

__int64 g_size = 2;

// найти комбинации
void findCombinations
(
    std::mutex *lock                // синхронизатор обновления данных
)
{
    int buffer[6];

    const __int64 data_max_size = 100000;
    int* data = new int[6 * data_max_size];

    while (true) {
        // получить задачу
        lock->lock();

        const __int64 size = g_size;
        g_size++;

        lock->unlock();

        // выполнить задачу
        __int64 data_max_pos = 0;

        const __int64 max_value = size * size * size * size * size * size;

        for (__int64 value = 0; value < max_value; value++) {
            __int64 tmp = value;

            for (__int64 i = 0; i < 6; i++) {
                buffer[i] = tmp % size;
                tmp /= size;
            }

            bool isSuccess = true;

            for (__int64 data_pos = 0; data_pos < data_max_pos; data_pos ++) {

                __int64 count = 0;

                for (__int64 i = 0; i < 6; i++) {
                    if (buffer[i] != data[data_pos * 6 + i])
                        count++;
                }

                if (count < 4) {
                    isSuccess = false;
                    break;
                }
            }

            if (isSuccess) {
                memcpy(data + data_max_pos * 6, buffer, sizeof(int) * 6);
                data_max_pos++;
            }
        }

        lock->lock();

        std::cout << size << "\t" << data_max_pos << std::endl;

        lock->unlock();
    }
}

int main() {

    // запустить потоки расчёта
    const int threadsAmount = 10;

    std::mutex lock;
    std::vector<std::thread> threads;

    for (int threadIndex = 0; threadIndex < threadsAmount; threadIndex++)
    {
        threads.push_back(std::thread(findCombinations, &lock));
    }

    // дождаться завершения потоков 
    for (auto& thread : threads)
    {
        if (thread.joinable())
            thread.join();
    }

    _getch();
    return 0;
}
13
  • я чуть скорректировал первый код и добавил еще один код - первый должен работать еще чуть-чуть побыстрее, на второй были большие надежды, но не оправдались :(
    – Zhihar
    Commented 13 дек. 2021 в 12:48
  • А верно ли обнулять "selected" внутри цикла(первый вариант кода)? Его можно вынести за цикл и тогда накопительно будут расти ряды, соответствующие требованиям Commented 13 дек. 2021 в 12:49
  • 1
    конечно нужно обнулять - мы же рассматриваем ситуации с разным кол-вом элементов как независимые, а если начнем накапливать, то получится треш
    – Zhihar
    Commented 13 дек. 2021 в 12:50
  • За полчаса досчитало до 16 -> 4096.
    – GrAnd
    Commented 13 дек. 2021 в 13:44
  • 1
    @splash58, в ответе добавил код на c++ как он выглядел (там пришлось свои оптимизации делать :)), нет - g_size - это число, изначально 2 - по сути текущая задача (кол-во разных символов) для первого потока, когда первый поток получает это число, он меняет глобальную переменную на 3, следующий поток берет уже 3 и меняет на 4 и т.д., причем когда происходит взятие задачи потоком остальные потоки продолжают работать, они блокируются только когда пытаются получить задачу (по сути синхронизация через критические секции)
    – Zhihar
    Commented 13 дек. 2021 в 19:51
1

Каждому коду можно сопоставить его номер в диапазоне [0, k^6), где k - размер алфавита. По количеству кодов создаётся булев массив - False - код свободен, True - занят. Коды перебираются лексикографически. Если код свободен, он печатается и помечается занятым. Занятыми также помечаются все коды в шаре радиуса три (в метрике Хемминга).

Метрика Хемминга. Способ когда коды перебираются лексикографически и помечаются - lexicode.

import itertools
import numpy as np


def index(k, x):
    i = 0
    for v in x:
        i = k * i + v
    return i


def codes(size, k, h):
    s = np.full((k ** size, ), False, dtype=bool)
    for i, p in enumerate(itertools.product(range(k), repeat=size)):
        if s[i]:
            continue

        yield i, p

        for c in itertools.combinations(range(size), h - 1):
            x = list(p)
            for pp in itertools.product(range(k), repeat=h - 1):
                for i, v in zip(c, pp):
                    x[i] = v
                s[index(k, x)] = True


k = int(input())
for i, p in codes(6, k, 4):
    print(i, ':', *p, flush=True)
              время                     время                     время  
      число   работы            число   работы            число   работы 
 k    кодов   (мин)        k    кодов   (мин)        k    кодов   (мин)  

 1        1    < 1        11      628    < 1        21     4542     13
 2        4    < 1        12      640    < 1        22     4928     16
 3       10    < 1        13     1057      1        23     5379     20
 4       64    < 1        14     1420      1        24     5632     24
 5       67    < 1        15     1805      2        25     6898     34
 6       88    < 1        16     4096      5        26     7970     44
 7      147    < 1        17     4099      6        27     9170     56
 8      256    < 1        18     4120      7        28     9408     64
 9      314    < 1        19     4194      9        29    11961     91
10      446    < 1        20     4288     10        30    13508    115

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.