Поиск множества максимально различных бинарных векторов из набора

Ответ 1

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

Например, алгоритм inc():

long  inc(long h_in , long m0 , long m1) {
    long  h_out = h_in | (~m1); //pre -mask
    h_out ++;
    // increment
    h_out = (h_out & m1) | m0; //post -mask
    return  h_out;
}

Он принимает вход h_in и возвращает следующее более высокое значение, которое по крайней мере на 1 больше h_in и "соответствует" границам m0 и m1. "Согласование" означает: результат имеет 1 whereever m0 имеет 1, и результат имеет 0 где m1 имеет 0. Не то, чтобы h_in ДОЛЖЕН быть действительным значением в отношении mo и m1 ! Также обратите внимание, что m0 должно быть поразмерно меньше, чем m1, что означает, что m0 не может иметь 1 в позиции, где m1 имеет значение 0.

Это можно использовать для создания перестановок с минимальным расстоянием редактирования до заданной входной строки:

Предположим, что у вас есть 0110, вы сначала НЕГАТИВАете его до 1001 (отредактируйте distance = k). Установите "m0 = 1001" и "m1 = 1001". Использование этого приведет только к самому "1001".

Теперь, чтобы получить все значения с расстоянием редактирования k-1, вы можете сделать следующее: просто переверните один из битов m0 или m1, затем inc() вернет упорядоченную серию всех битовых строк, имеющих разность k или k-1.

Я знаю, еще не очень интересно, но вы можете изменить до k бит, и inc() всегда будет возвращать все перестановки с максимально допустимой разницей редактирования в отношении m0 и m1.

Теперь, чтобы получить все перестановки, вам придется повторно запустить алгоритм со всеми возможными комбинациями m0 и m1.

Пример. Чтобы получить все возможные перестановки 0110 с расстоянием редактирования 2, вам нужно будет запустить inc() со следующими перестановками m0=0110 и m1=0110 (для получения перестановок необходимо разбить битовую позицию, что означает, что m0 устанавливается в 0 а m1 устанавливается в 1:

• Бит 0 и 1 расширен: m0=0010 и m1=1110
• Бит 0 и 2 расширен: m0=0100 и m1=1110
• Бит 0 и 3 расширен: m0=0110 и m1=1111
• Бит 1 и 2 расширены: m0=0000 и m1=0110
• Бит 1 и 3 расширены: m0=0010 и m1=0111
• Бит 2 и 3 расширены: m0=0100 и m1=0111

В качестве начального значения для h_0 я предлагаю использовать просто m0. Итерация может быть прервана после того, как inc() вернет m1.

Резюме. Вышеупомянутый алгоритм генерирует в O (x) все x двоичных векторов, которые отличаются по меньшей мере y битами (настраиваемыми) от заданного вектора v.

Используя ваше определение n= number of bits in a vector v, установка y=n генерирует ровно 1 вектор, который является точным противоположным вектору v. Для y=n-1 он будет генерировать n+1 векторов: n векторов, которые различаются во всех, кроме одного бита и 1 вектора, который отличается во всех битах. И так на разных значениях y.

** EDIT: добавлено резюме и заменено ошибочное "XOR" на "NEGATE" в тексте выше.

Ответ 2

Я не знаю, является ли максимизация суммы расстояний Хэмминга лучшим критерием для получения набора "максимально разных" двоичных векторов, но я сильно подозреваю, что это так. Кроме того, я сильно подозреваю, что алгоритм, который я собираюсь представить, дает ровно множество k векторов, которые максимизируют сумму расстояний Хэмминга для векторов n бит с m единиц и n - m нулей. К сожалению, у меня нет времени, чтобы это доказать (и, конечно, я могу ошибаться - в этом случае у вас останется "субоптимальное, но хорошее" решение, согласно вашему запросу.)

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

Предлагаемый алгоритм следующий:

Начиная с набора результатов только одним вектором, повторно добавляйте один из тех оставшихся векторов, у которых максимальная сумма расстояний Хэмминга от всех векторов, которые уже находятся в наборе результатов. Остановите, когда набор результатов содержит k векторов или все доступные векторы.

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

Я нашел подход "грубой силы" жизнеспособным, учитывая ограничения, упомянутые в комментарии:

n <25, 1 <m <10, 10 <k <100 (или 10 <k <50)

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

Вот мое решение на Java. Он должен быть легко переводимым на любой процедурный язык, если это необходимо. Часть, которая вычисляет комбинации m элементов из n, может быть заменена вызовом библиотеки, если она доступна. Следующие Java-методы имеют соответствующий макрос C/C++, который использует быстрые специализированные инструкции процессора для современных процессоров: Long.numberOfTrailingZeros → __builtin_ctzl, Long.bitCount → __builtin_popcountl.

package waltertross.bits;

public class BitsMain {

    private static final String USAGE =
        "USAGE: java -jar <thisJar> n m k (1<n<64, 0<m<n, 0<k)";

    public static void main (String[] args) {

        if (args.length != 3) {
            throw new IllegalArgumentException(USAGE);
        }
        int n = parseIntArg(args[0]); // number of bits
        int m = parseIntArg(args[1]); // number of ones
        int k = parseIntArg(args[2]); // max size of result set
        if (n < 2 || n > 63 || m < 1 || m >= n || k < 1) {
            throw new IllegalArgumentException(USAGE);
        }
        // calculate the total number of available bit vectors
        int c = combinations(n, m);
        // truncate k to the above number
        if (k > c) {
            k = c;
        }
        long[] result   = new long[k]; // the result set (actually an array)
        long[] vectors  = new long[c - 1]; // all remaining candidate vectors
        long[] hammingD = new long[c - 1]; // their total Hamming distance to the result set
        long firstVector = (1L << m) - 1; // m ones in the least significant bits
        long lastVector  = firstVector << (n - m); // m ones in the most significant bits
        result[0] = firstVector; // initialize the result set
        // generate the remaining candidate vectors in "lexicographical" order
        int size = 0;
        for (long v = firstVector; v != lastVector; ) {
            // See http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
            long t = v | (v - 1); // t gets v least significant 0 bits set to 1
            // Next set to 1 the most significant bit to change,
            // set to 0 the least significant ones, and add the necessary 1 bits.
            v = (t + 1) | (((~t & -~t) - 1) >>> (Long.numberOfTrailingZeros(v) + 1));
            vectors[size++] = v;
        }
        assert(size == c - 1);
        // chosenVector is always the last vector added to the result set
        long chosenVector = firstVector;
        // do until the result set is filled with k vectors
        for (int r = 1; r < k; r++) {
            // find the index of the new chosen vector starting from the first
            int chosen = 0;
            // add the distance to the old chosenVector to the total distance of the first
            hammingD[0] += Long.bitCount(vectors[0] ^ chosenVector);
            // initialize the maximum total Hamming distance to that of the first
            long maxHammingD = hammingD[0];
            // for all the remaining vectors
            for (int i = 1; i < size; i++) {
                // add the distance to the old chosenVector to their total distance
                hammingD[i] += Long.bitCount(vectors[i] ^ chosenVector);
                // whenever the calculated distance is greater than the max,
                // update the max and the index of the new chosen vector
                if (maxHammingD < hammingD[i]) {
                    maxHammingD = hammingD[i];
                    chosen = i;
                }
            }
            // set the new chosenVector to the one with the maximum total distance
            chosenVector = vectors[chosen];
            // add the chosenVector to the result set
            result[r] = chosenVector;
            // fill in the hole left by the chosenVector by moving all vectors
            // that follow it down by 1 (keeping vectors and total distances in sync)
            System.arraycopy(vectors,  chosen + 1, vectors,  chosen, size - chosen - 1);
            System.arraycopy(hammingD, chosen + 1, hammingD, chosen, size - chosen - 1);
            size--;
        }
        // dump the result set
        for (int r = 0; r < k; r++) {
            dumpBits(result[r], n);
        }
    }

    private static int parseIntArg(String arg) {
        try {
            return Integer.parseInt(arg);
        } catch (NumberFormatException ex) {
            throw new IllegalArgumentException(USAGE);
        }
    }

    private static int combinations(int n, int m) {
        // calculate n over m = n! / (m! (n - m)!)
        // without using arbitrary precision numbers
        if (n <= 0 || m <= 0 || m > n) {
            throw new IllegalArgumentException();
        }
        // possibly avoid unnecessary calculations by swapping m and n - m
        if (m * 2 < n) {
            m = n - m;
        }
        if (n == m) {
            return 1;
        }
        // primeFactors[p] contains the power of the prime number p
        // in the prime factorization of the result
        int[] primeFactors = new int[n + 1];
        // collect prime factors of each term of n! / m! with a power of 1
        for (int term = n; term > m; term--) {
            collectPrimeFactors(term, primeFactors, 1);
        }
        // collect prime factors of each term of (n - m)! with a power of -1
        for (int term = n - m; term > 1; term--) {
            collectPrimeFactors(term, primeFactors, -1);
        }
        // multiply the collected prime factors, checking for overflow
        int combinations = 1;
        for (int f = 2; f <= n; f += (f == 2) ? 1 : 2) {
            // multiply as many times as requested by the stored power
            for (int i = primeFactors[f]; i > 0; i--) {
                int before = combinations;
                combinations *= f;
                // check for overflow
                if (combinations / f != before) {
                    String msg = "combinations("+n+", "+m+") > "+Integer.MAX_VALUE;
                    throw new IllegalArgumentException(msg);
                }
            }
        }
        return combinations;
    }

    private static void collectPrimeFactors(int n, int[] primeFactors, int power) {
        // for each candidate prime that fits in the remaining n
        // (note that non-primes will have been preceded by their component primes)
        for (int i = 2; i <= n; i += (i == 2) ? 1 : 2) {
            while (n % i == 0) {
                primeFactors[i] += power;
                n /= i;
            }
        }
    }

    private static void dumpBits(Long bits, int nBits) {
        String binary = Long.toBinaryString(bits);
        System.out.println(String.format("%"+nBits+"s", binary).replace(' ', '0'));
    }
}

Данные алгоритма для n = 5, m = 2, k = 4:

result
00011   00101 00110 01001 01010 01100 10001 10010 10100 11000 vectors
          0→2   0→2   0→2   0→2   0→4   0→2   0→2   0→4   0→4 hammingD
                                    ^                         chosen
00011   00101 00110 01001 01010 10001 10010 10100 11000
01100     2→4   2→4   2→4   2→4   2→6   2→6   4→6   4→6
                                    ^
00011   00101 00110 01001 01010 10010 10100 11000
01100     4→6   4→8   4→6   4→8   6→8   6→8   6→8
10001             ^

00011   00101 01001 01010 10010 10100 11000
01100       6     6     8     8     8     8
10001
00110

Выход образца (n = 24, m = 9, k = 20):

[wtross ~/Dropbox/bits]$ time java -jar bits-1.0-SNAPSHOT.jar 24 9 20
000000000000000111111111
000000111111111000000000
111111000000000000000111
000000000000111111111000
000111111111000000000000
111000000000000000111111
000000000111111111000000
111111111000000000000000
000000000000001011111111
000000111111110100000000
111111000000000000001011
000000000000111111110100
001011111111000000000000
110100000000000000111111
000000001011111111000000
111111110100000000000000
000000000000001101111111
000000111111110010000000
111111000000000000001101
000000000000111111110010

real    0m0.269s
user    0m0.244s
sys     0m0.046s

Самый сложный случай в ваших ограничениях (n = 24, m = 9, k = 99) занимает около 550 мс на моем Mac.

Некоторая оптимизация алгоритма может быть выполнена еще быстрее, например, путем смещения более коротких кусков массива. Примечательно, что в Java я обнаружил смещение "вверх" значительно медленнее, чем смещение "вниз".

Ответ 3

ОБНОВЛЕННЫЙ ОТВЕТ

Рассматривая пример вывода кода Уолтера Тросса, я думаю, что создание случайного решения можно упростить:

Возьмите любой вектор для начала, например, для n = 8, m = 3, k = 5:

A:   01001100  

После каждого шага суммируйте векторы, чтобы получить количество раз, когда использовалась каждая позиция:

SUM: 01001100

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

B:   00110001

получить:

A:   01001100  
B:   00110001
SUM: 01111101  

Затем осталось 2 наименее используемых положения, поэтому для 3-х в следующем векторе используйте эти 2 позиции, а затем поместите третий в любом месте:

C:   10010010

получить:

A:   01001100  
B:   00110001
C:   10010010
SUM: 11121111  (or reset to 00010000 at this point)  

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

D:   10100010

получить:

A:   01001100  
B:   00110001
C:   10010010
D:   10100010
SUM: 21221121  

И для конечного вектора выберите любую из 4 наименее используемых позиций, например:

E:   01000101

Чтобы генерировать все решения, просто сгенерируйте каждый возможный вектор на каждом шаге:

A:   11100000, 11010000, 11001000, ... 00000111

Затем, например, когда A и SUM равны 11100000:

B:   00011100, 00011010, 00011001, ... 00000111

Затем, например, когда B - 00011100, а SUM - 11111100:

C:   10000011, 01000011, 00100011, 00010011, 00001011, 00000111

Затем, например, когда C - 10000011, а SUM - 21111111:

D:   01110000, 01101000, 01100100, ... 00000111

И, наконец, например, когда D равно 01110000, а SUM - 22221111:

E:   00001110, 00001101, 00001011, 00000111

Это привело бы к C (8,3) × C (5,3) × C (8,1) × C (7,3) × C (4,3) = 56 × 10 × 8 × 35 × 4 = 627 200 решения для n = 8, m = 3, k = 5.

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

НАЧАЛЬНЫЙ ОТВЕТ - ОСНОВНЫЕ ВОПРОСЫ

(Я предполагаю, что m не больше n/2, т.е. Число единиц не больше числа нулей. В противном случае используйте симметричный подход.)

Когда k × m не больше n, то, очевидно, существуют оптимальные решения, например:

n=10, m=3, k=3:  
A: 1110000000  
B: 0001110000  
C: 0000001110  

где расстояния Хэмминга равны 2 × м:

|AB|=6, |AC|=6, |BC|=6, total=18

Когда k × m больше n, решения, в которых минимизирована разность расстояний Хэмминга между последовательными векторами, дают наибольшее общее расстояние:

n=8, m=3, k=4:
A: 11100000
B: 00111000
C: 00001110
D: 10000011
|AB|=4, |AC|=6, |AD|=4, |BC|=4, |BD|=6, |CD|=4, total=28  

n=8, m=3, k=4:
A: 11100000
B: 00011100
C: 00001110
D: 00000111
|AB|=6, |AC|=6, |AD|=6, |BC|=2, |BD|=4, |CD|=2, total=26  

Итак, практически, вы берете m × k и видите, насколько это больше, чем n, пусть назовите его x = m × k-n, и это x - количество перекрытий, то есть, как часто вектор будет иметь один в такое же положение, что и предыдущий вектор. Затем вы распределяете перекрытие по различным векторам максимально равномерно, чтобы максимизировать общее расстояние.

В приведенном выше примере x = 3 × 4-8 = 4, и у нас есть 4 вектора, поэтому мы можем равномерно распределить перекрытие, и каждый вектор имеет 1 в том же положении, что и предыдущий вектор.

Чтобы создать все уникальные решения, вы можете:

• Вычислите x = m × k-n и сгенерируйте все разбиения x на k частей с минимально возможным максимальным значением:

n=8, m=3, k=5  ->  x=7  
22111, 21211, 21121, 21112, 12211, 12121, 12112, 11221, 11212, 11122  
(discard partitions with value 3)  

• Сгенерируйте все векторы, которые будут использоваться в качестве вектора A, например:

A: 11100000, 11010000, 11001000, 11000100, ... 00000111

• Для каждого из них генерируем все векторы B, которые лексикографически меньше, чем вектор A, и имеют правильное количество перекрывающихся с вектором A (в примере, равном 1 и 2), например:

A: 10100100
overlap=1:  
B: 10011000, 10010010, 10010001, 10001010, 10001001, 10000011, 01110000, ... 00000111
overlap=2:  
B: 10100010, 10100001, 10010100, 10001100, 10000110, 10000101, 01100100, ... 00100101  

• Для каждого из них генерируем все векторы C и т.д. До тех пор, пока вы не наберете k векторов. При генерации последнего вектора вы должны учитывать совпадение с предыдущим, а также с первым (т.е. первым) вектором.

Я считаю, что лучше всего рассматривать разбиения x на k как двоичное дерево:

                   1                                      2
      11                      12                    21         22
111        112           121       122        211       212    221
1112   1121   1122   1211   1212   1221   2111   2112   2121   2211
11122  11212  11221  12112  12121  12211  21112  21121  21211  22111

и пересекайте это дерево при создании решений, так что каждый вектор нужно генерировать только один раз.

Я думаю, что этот метод работает только для некоторых значений n, m и k; Я не уверен, что это можно сделать для общего дела.