Выберите самые разные элементы в массиве

Question

У меня есть текстовый файл с P случайными записями в Binary (или Hex) для обработки, из этого числа P, я должен взять N записей так, чтобы они были самыми разными между ними поэтому у меня есть хороший представитель возможного населения.

До сих пор, я думаю о сделать сравнение между текущим N, и среднее значение массива, который содержит элементы, используя модифицированную версию алгоритма в: How do I calculate similarity of two integers?

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

Я не знаю, есть ли лучшее решение к этому.

Ex.

[00011111, 00101110, 11111111, 01001010, 00011000, 10010000, 01110101]

P = 7 N = 3

Результат: [00011111, 10010000, 00101110]

Заранее спасибо

Answer 1

Вы можете рассчитать расстояния Хэмминга для всех комбинаций, если вы хотите выбрать наиболее различное двоичное представление (см. https://en.wikipedia.org/wiki/Hamming_distance).

Edit: маленький хак

import numpy as np 

a = [0b00011111, 0b00101110, 0b11111111, 0b01001010, 0b00011000, 0b10010000, 0b01110101] 
N = 3 

b = [] 
for i in a: 
    b.append(np.unpackbits(np.uint8(i))) #to binary representation 


valuesWithBestOverallDiffs = [] 

def getItemWithBestOverallDiff(b): 
    itemWithBestOverallDiff = [0, 0] #idx, value 

    for biter, bval in enumerate(b): 
     hammDistSum = 0 
     for biter2, bval2 in enumerate(b): 
      if biter == biter2: 
       continue 
      print("iter1: " + str(biter) + " = " + str(bval)) 
      print("iter2: " + str(biter2) + " = " + str(bval2)) 
      hammDist = len(np.bitwise_xor(bval, bval2).nonzero()[0]) 
      print(" => " + str(hammDist)) 
      hammDistSum = hammDistSum + hammDist 

     if hammDistSum > itemWithBestOverallDiff[1]: 
      itemWithBestOverallDiff = [biter, hammDistSum] 

    #print(itemWithBestOverallDiff) 
    return itemWithBestOverallDiff 


for i in range(N): 
    itemWithBestOverallDiff = getItemWithBestOverallDiff(b) 
    print("adding item nr " + str(itemWithBestOverallDiff[0]) + " with value 0b" + str(b[itemWithBestOverallDiff[0]]) + " = " + str(a[itemWithBestOverallDiff[0]])) 
    val = a.pop(itemWithBestOverallDiff[0]) 
    b.pop(itemWithBestOverallDiff[0]) 
    valuesWithBestOverallDiffs.append(val) 

print("result: ") 
print(valuesWithBestOverallDiffs) 

Окончательный вывод результат: [144, 117, 255]

который 0b10010000, 0b01110101, 0b11111111

Answer 2

Вы должны сравнить их Pairwise , эта проблема сравнения - самая короткая общая проблема суперсимметрии (см. this). кратчайшая общая суперсимметрия строк x и y является кратчайшей z такой, что x и y являются подпоследовательностями z. Кратчайшая общая суперсимметрия - проблема, тесно связанная с самой длинной общей подпоследовательностью (см. enter link description here). Лучшим решением для самой длинной общей подпоследовательности является метод динамического программирования.