Kombinatorik mit Binärwerten

[kodela]

Hallo,

kann mir jemand sagen, wie man am einfachsten alle Binärwerte erzeugen kann, die zum Beispiel 12 Stellen und zwei geswetzte Digits haben. Also zum Beispiel 0b11, 0b101, 110, ... 110000000000.

Allgemeiner gesagt suche ich eine Lösung für eine feste Länge (12 Digits) und eine variable Anzahl gesetzter Digits (von 2 bis 10), die der Reihe nach erzeugt werden können. Für zwei Digits müssten es 66, für drei 220, für vier 495, für fünf 792 und für sech 924 Kombinationen sein. Danach geht es wieder abwärts, bei 10 Digits sind es dann wieder 66 Kombinationen, wenn ich richtig gerechnet habe.

MfG, kodela

[BlackJack]

Das `itertools`-Modul hat da die `combinations()`-Funktion:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
from itertools import combinations, imap
from operator import or_


def iter_bit_combinations(width, bit_count):
    return imap(
        lambda xs: reduce(or_, xs, 0),
        combinations([2**i for i in xrange(width)], bit_count)
    )


def main():
    width = 12
    for bit_count in xrange(2, 11):
        print(
            bit_count, sum(1 for _ in iter_bit_combinations(width, bit_count))
        )

    for value in iter_bit_combinations(width, 2):
        print('{0:0{1}b}'.format(value, width))


if __name__ == '__main__':
    main()

Ausgabe:

Code: Alles auswählen

2 66
3 220
4 495
5 792
6 924
7 792
8 495
9 220
10 66
000000000011
000000000101
000000001001
000000010001
000000100001
000001000001
000010000001
000100000001
001000000001
010000000001
100000000001
000000000110
000000001010
000000010010
000000100010
000001000010
000010000010
000100000010
001000000010
010000000010
100000000010
000000001100
000000010100
000000100100
000001000100
000010000100
000100000100
001000000100
010000000100
100000000100
000000011000
000000101000
000001001000
000010001000
000100001000
001000001000
010000001000
100000001000
000000110000
000001010000
000010010000
000100010000
001000010000
010000010000
100000010000
000001100000
000010100000
000100100000
001000100000
010000100000
100000100000
000011000000
000101000000
001001000000
010001000000
100001000000
000110000000
001010000000
010010000000
100010000000
001100000000
010100000000
100100000000
011000000000
101000000000
110000000000

[kodela]

Hallo BlackJack,

danke für Deine Hinweise. Sieht sehr gut aus. Im Augenblick kann ich mich nur noch nicht damit beschäftigen. Aber das kommt noch.

MfG, kodela

[kodela]

Hallo BlackJack,

ich weiß, es ist unbescheiden, aber da Du mit Python doch tausendmal besser vertraut bist, als ich blutiger Anfänger, möchte ich noch eine Bitte nachschieben.

Wie kann man, so elegant wie Deine erste Lösung ist, die einzelnen Digits als Positionswerte in eine Liste schreiben, also zum Beispiel für die Digits in 0b000000100101 die Positionswerte [5, 2, 0] ?

Die Lösung, die mir dazu einfällt, ist vermutlich wesentlich umständlicher, als es unter Python möglich ist.

MfG, kodela

[Sirius3]

@kodela: schau Dir mal die Dokumentation zu combinations an.

[Hyperion]

Die Lösung, die mir dazu einfällt, ist vermutlich wesentlich umständlicher, als es unter Python möglich ist.

Poste sie doch dennoch! Evtl. ist die ja bereits effizient und sogar elegant Auf jeden Fall zeigt es, dass Du Dich damit befasst. Hausaufgaben vorkauen mögen wir hier nicht so, d.h. es gibt eher Hilfe zur Selbsthilfe!

[kodela]

@Hyperion:

Ok, damit Du nicht denkst, ich lasse mir von anderen meine Hausaufgaben machen. Hier der Code, so wie ich es mir gedacht habe. Da ich mich aber erst seit gut drei Wochen mit Python beschäftige, dachte ich mir, es wäre keine schlechte Idee, Leute zu fragen, die Python wesentlich besser kennen, als ich. Daraus kann man ja lernen. Wenn man aber wegen jeder Frage schief angesehen wird, dann frage ich mich schon, für was dann ein Forum gut sein soll.

Code: Alles auswählen

for value in iter_bit_combinations(width, 2):
    for i in range(12):
        d = 1 << i
        if value & d > 0:
            print ('gesuchter Index fuer ', value, 'ist' , i)
    print ('\n')

Und hier die Ausgabe für die ersten fünf Kombinationen.

Code: Alles auswählen

gesuchter Index fuer  3 ist 0
gesuchter Index fuer  3 ist 1

gesuchter Index fuer  5 ist 0
gesuchter Index fuer  5 ist 2

gesuchter Index fuer  9 ist 0
gesuchter Index fuer  9 ist 3

gesuchter Index fuer  17 ist 0
gesuchter Index fuer  17 ist 4

gesuchter Index fuer  33 ist 0
gesuchter Index fuer  33 ist 5

MfG, kodela

[kodela]

@kodela: schau Dir mal die Dokumentation zu combinations an.

Danke für den Hinweis auf die Dokumentation. Obwohl ich leider in der Schule nie Englisch gelernt habe (Jahrgang 38) und alle späteren Versuche dies nachzuholen nicht sehr erfolgreich waren, habe ich versucht, aus der Dokumentation etwas für mein Problem herauszufinden, vor allem aber auch, wenigstens den Code von BlackJack zu verstehen. Alles was ich fand waren neue Fragen. Nach drei Wochen mit Python ist speziell der von Dir verlinkte Teil für mich noch zu hoch.

Ausserdem habe ich mir in einem deutschsprachigem Forum nicht unbedingt nur Verweise auf englische Dokumentationen erhofft.

MfG, kodela

[Sirius3]

@kodela: Dein Problem hat halt was mit Kombinatorik zu tun, die Funktion combinations hilft dabei, und die Dokumentation ist sehr illustrativ - die Lingua franca der Informatik ist nunmal Englisch.
Die Lösung, die nur mit einfachen Sprachmitteln auskommt, wäre viel komplizierter, da sie für jede Anzahl an Bits mehr verschachtelte for-Schleifen benötigt:

Code: Alles auswählen

for a in range(11):
    for b in range(a+1, 12):
        print(a, b)

statt einfach nur

Code: Alles auswählen

for indizes in itertools.combinations(range(12), 2):
    print(indizes)

wobei hier 2 durch jede beliebige andere Zahl zwischen 1 und 12 ersetzt werden kann.

[kodela]

@Sirius3:
Danke, das war es. Durch Deinen Hinweis ist mir nicht nur ein Licht sondern eine ganze Lichterkette aufgegangen.

MfG, kodela