Как понять какое кол-во элементов нужно взять, чтобы получить 9000 рядов из 6 знаков (типа [1, 1, 1, 1, 1, 1]), чтобы отличались минимум на 4 знака?

такой код работает побыстрее, но тоже до 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;
}

Каждому коду можно сопоставить его номер в диапазоне [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