Wählen Sie die unterschiedlichsten Elemente in einem Array

Question

Ich habe einen Datei-Text mit P zufällige Einträge in Binär (oder Hex) für die Verarbeitung, von dieser P-Nummer muss ich N Einträge so unterschiedlich wie möglich nehmen so habe ich einen guten Vertreter der möglichen Bevölkerung.

Bisher habe ich denke, der einen Vergleich zwischen dem aktuellen N tun, und ein Durchschnitt des Array, das die Elemente unter Verwendung einer modifizierten Version des Algorithmus enthält in: How do I calculate similarity of two integers?

oder eine kumulative Punktzahl der Ähnlichkeit mit (Je höher die am meisten Unterschied) zwischen dem nächsten Element ausgewählt werden und alle Elemente im Array, und wählen Sie die nächste, und wiederholen, bis die gewünschte N

Ich weiß nicht, ob es eine bessere Lösung ist dazu.

Ex.

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

P = 7 N = 3

Ergebnis: [00011111, 10010000, 00101110]

Vielen Dank im Voraus

Answer 1

Sie können die Hamming-Abstände für alle Kombinationen berechnen, wenn Sie die unterschiedlichste binäre Darstellung wählen möchten (siehe https://en.wikipedia.org/wiki/Hamming_distance).

Edit: kleine Hack

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) 

Der endgültige Ausgang ist Ergebnis: [144, 117, 255]

die 0b10010000 ist, 0b01110101, 0b11111111

Answer 2

Sie sollten sie vergleichen Pairwise . Dieses Vergleichsproblem ist das kürzeste gemeinsame Supersequenzproblem (siehe this). eine kürzeste gemeinsame Supersequenz der Ketten x und y ist eine kürzeste Kette z, so dass sowohl x als auch y Teilsequenzen von z sind. Die kürzeste gemeinsame Supersequenz ist ein Problem, das eng mit der längsten gemeinsamen Subsequenz zusammenhängt (siehe enter link description here). Die beste Lösung für die längste gemeinsame Teilsequenz ist die dynamische Programmiermethode.