Was ist ein schneller Weg, um die n-te Ganzzahl> 0 zu erhalten, die höchstens k Bits gesetzt hat?

Question

Ich habe eine Reihe, Werte größer als 0, wobei die Anzahl der gesetzten Bits nicht mehr k ist.

for instance, for `k = 2` 

n binary value bits_set 
0 0000  0  0 
1 0001  1  1 
2 0010  2  1 
3 0011  3  2 
4 0100  4  1 
5 0101  5  2 
6 0110  6  2 
7 1000  8  1 
8 1001  9  2 
9 1010  10  2 
10 1100  14  2 
... etc ... 

Gibt es eine rechnerisch effiziente Weise die n -te Element in der Serie für einen gegebenen Wert von k zu finden?

Alle meine Versuche hatten eine sehr langsame Leistung und ich weiß nicht, wie ich das Problem effizient angehen soll.

Answer 1

weiß, dass ich die Frage markiert ist C#, Entschuldigungen zu geben, eine Antwort in Python:

Zunächst werden wir einen Weg zu zählen, wie viele verschiedene Zahlen gibt es mit einer bestimmten Anzahl von Bits aus einem verfügbaren Platz finden . Dann werden wir einen Weg finden, diese Ergebnisse zu ordnen.

Bezeichnen Sie f (b, s) als die Anzahl der Möglichkeiten zum Aufbau einer Zahl mit genau s Bits aus b gesetzt.

Hier besteht eine Wiederholungsbeziehung. Eine Zahl, die f (b, s) erfüllt, ist entweder eine Zahl, die f (b-1, s) mit einer 0 auf der Vorderseite erfüllt, oder eine Zahl, die f (b-1, s-1) mit einer 1 auf der Vorderseite erfüllt. Daher ist f (b, s) = f (b-1, s) + f (b-1, s-1).

Einige Basis Fälle in dieser Tabelle ausfüllen: f (b, 0) 1 f (b, s) 1, wo s b =

10 9 8 7 6 5 4 3 2 1 0 
24 . . . . . . . . . . 1 
23 . . . . . . . . . . 1 
22 . . . . . . . . . . 1 
21 . . . . . . . . . . 1 
20 . . . . . . . . . . 1 
19 . . . . . . . . . . 1 
18 . . . . . . . . . . 1 
17 . . . . . . . . . . 1 
16 . . . . . . . . . . 1 
15 . . . . . . . . . . 1 
14 . . . . . . . . . . 1 
13 . . . . . . . . . . 1 
12 . . . . . . . . . . 1 
11 . . . . . . . . . . 1 
10 1 . . . . . . . . . 1 
9 0 1 . . . . . . . . 1 
8 0 0 1 . . . . . . . 1 
7 0 0 0 1 . . . . . . 1 
6 0 0 0 0 1 . . . . . 1 
5 0 0 0 0 0 1 . . . . 1 
4 0 0 0 0 0 0 1 . . . 1 
3 0 0 0 0 0 0 0 1 . . 1 
2 0 0 0 0 0 0 0 0 1 . 1 
1 0 0 0 0 0 0 0 0 0 1 1 

Es wird nützlich sein, auch die bauen Tabelle g (b, s), die angibt, wie viele b-Bit-Zahlen s oder weniger Bits gesetzt haben. g (b, s) = summe (i = 0 bis s) f (b, i)

So können wir jetzt die Frage beantworten, wie viele Zahlen es gibt mit genau 10 Bits von 24 gesetzt, das ist f (24, 10) = 1961256, und wir können beantworten, wie viele Zahlen es gibt mit höchstens 10 Bits von 24, das ist f (24, 10) + f (24, 9) + f (24, 8) ... + f (24, 1) + f (24, 0) = g (24, 10) = 4540386

Aber wenn die Frage ist, die n-te Nummer so zu finden, dass höchstens 10 von 24 Bits gesetzt sind, Wir müssen in der Lage sein, diesen Raum in einer geordneten Weise zu suchen.

Beachten Sie zunächst, dass jede Zahl mit ihrer ersten 1 im n-ten Bit größer ist als jede Zahl mit ihrer ersten 1 in irgendeinem Bit später als n.

Dies bedeutet, dass wir die Position jeder Zahl mit nur einem einzigen Bitsatz gefolgt von z Nullen finden können. Das ist notwendigerweise größer als g (z, max (z, 10)). Wir können eine Optimierung hier einfügen und feststellen, dass, da alle Zahlen in einem 10-Bit-Raum geeignet sind (sie können möglicherweise nicht mehr als 10 Bits gesetzt haben), dann die n-te Zahl = n für alle n < = 2^10.

Wenn n> 2^10 (=> z> 10) können wir nach dem Ort des ersten gesetzten Bits suchen, indem wir den größten z_10 so finden, dass g (z_10, 10) < = n ist. Wenn es tatsächlich gleich n ist, haben wir unsere Antwort gefunden, damit wir aufhören können. Wenn wir hypereffizient sein wollen, kann dies sogar durch binäre Suche geschehen!

Andernfalls müssen wir den größten z_9 so dass g (z_9, 9) < = n - g (z_10, 10), dann ist die größte z_8, so dass g (z_8, 8) < = n - g (z_10 , 10) - g (z_9, 9) und so weiter, bis wir unsere Gleichheit treffen und die Frage beantwortet haben.

In Python:

class Memoize: 
    def __init__(self, f): 
     self.f = f 
     self.memo = {} 
    def __call__(self, *args): 
     if not args in self.memo: 
      self.memo[args] = self.f(*args) 
     return self.memo[args] 

def g(b, s): 
    r = 0 
    for i in range(0, s+1): 
     r = r + f(b, i) 
    return r 

def f(b,s): 
    if b == s: 
     return 1 
    if s == 0: 
     return 1 
    if b < s: 
     return 0 
    return f(b-1, s) + f(b-1, s-1) 

def build(s, n, i): 
    d = (24 - len(s)) 
    if n <= 2 ** i: 
     return s + format(n, '0%db' % (d)) 
    for z in range(i, d+1): 
     x = g(z, i) 
     if x < n: 
      continue 
     if x == n: 
      return s + format(2 ** z, '0%db' % (d)) 
     y = g(z-1, i) 
     return build(s + format(1, '0%db' % (d-(z-1))), 
        n - y, 
        i - 1) 

def solve(n): 
    return build("", n-1, 10) 

f = Memoize(f) 
g = Memoize(g) 

for n in range(1, 4540387): 
    print("%07d: %s" % (n, solve(n)))