Wie finden Sie alle Bitmask-Kombinationen gegebenen i nachfolgenden Werte kann "0", j kann "1" sein?

Question

Eingabe.
Ich habe ein Bit-Array-Größe n und zwei ganze Zahlen, 1<=i<=n und 0<=j<=n. i gibt das Maximum der nachfolgenden Nummern an, die 0 sein können. j gibt das Maximum der nachfolgenden Nummern an, die 1 sein können.

gewünschte Ausgabe
ich nach einer Methode suchen, die alle möglichen Bit-Arrays n, die diese Einschränkungen erfüllen Größe zurückgibt.

Das Durchschleifen aller Array-Kombinationen (zuerst ohne Einschränkungen) würde zu einer exponentiellen Zeit führen. (Besonders wenn i/j>>1. Ich nehme an, Sie können es besser machen). Wie kann ich diese Bitmaskenkombinationen effektiv finden?

Beispiel
Eingang: i = 1, j = 2, n = 3

Ergebnis: Mögliche Arrays sind [0,1,0], [1,0,1],[1,1,0],[0,1,1].

Answer 1

Das ist ein schönes Problem für dynamische Programmierlösung. Es ist genug, um eine Methode zu haben, die die Anzahl der Strings zurückgibt, beginnend mit der gegebenen Ziffer (0 oder 1) mit der gegebenen Länge. Als Anzahl der Stellen der Länge n ist die Summe von Strings mit 0 und beginnend mit 1.

Einfache Python-Lösung mit memoization Start ist:

_c = {} # Cache 

def C(d, n, ij): 
    if n <= 1: 
     return 1 
    if (d, n) not in _c: 
     _c[(d, n)] = sum(C(1-d, n-x, ij) for x in xrange(1, min(ij[d], n)+1)) 
    return _c[(d, n)] 

def B(n, i, j): 
    ij = [i, j] # Easier to index 
    _c.clear() # Clears cache 
    return C(0, n, ij) + C(1, n, ij) 

print B(3, 1, 2) 
print B(300, 10, 20) 

Ergebnis ist:

4 
1896835555769011113367758506440713303464223490691007178590554687025004528364990337945924158 

Seit Wert für Die gegebene Zahl und die Länge hängen von den Werten der entgegengesetzten Zahl und der Länge ab, die kleiner als die gegebene Länge ist, die Lösung kann man auch bekommen, indem man die Werte in zunehmendem Maße nach der Länge berechnet. Python-Lösung:

def D(n, i, j): 
    c0 = [1] # Initialize arrays 
    c1 = [1] 
    for x in xrange(1, n+1): # For each next digit calculate value 
     c0.append(sum(c1[x-y] for y in xrange(1, min(i, x)+1))) 
     c1.append(sum(c0[x-y] for y in xrange(1, min(j, x)+1))) 
    return c0[-1] + c1[-1] # Sum strings starting of length n with 0 and 1 

print D(3, 1, 2) 
print D(300, 10, 20) 

Späterer Ansatz ist einfacher in C++ zu implementieren.