Zahlen auf bestimmte Art durchgehen

Hallo,

ich suche einen Algorithmus, mit dem ich Zahlen von n..0 durchgehen
kann - dabei soll die Reihenfolge so sein, dass die Anzahl der
Einsen in der binären Darstellung der Zahl monotion fällt.

BSP

111 (3 einser)
011 (2 einser)
110 "
101 "
001 (1 einser)
010 "
100 "
000 (0 einser)

Die Reihenfolge innerhalb eines bereichs ist egal.

Ideen?

Gruss,
Stefan

Hallo !

zahlen_sortierender schrieb:

..

Ideen?
..

Ja.

Du ziehst von n bei jedem Schritt den Wert 1 ab.

damit bekomme ich die Reihenfolge

101 (2)
100 !! fehler - (1)
011 (2)
010
001

Geht also nicht.

Wieso ? Die Anzahl ist doch monoton gefallen.

Wofür brauchst du das.

Hi,
Du löscht das n-te Bit von links und permutierst diese Bitfolge durch. Dann löscht du das n+1-te Bit von links und permutierst erneut.

Numwalker schrieb:

Wieso ? Die Anzahl ist doch monoton gefallen.

wenn nach 100 (eine 1) 011 (2 einsen) kommt, dann ist das weder gefallen noch
im gesamten kontext monoton...

Immernoch nicht wissen warum du wolle das machene.

Was seinlos mit tipp von der Permutarererererererererererer ?
Nix gut nix klappene ?

Mfg

Permutarererere schrieb:

Hi,
Du löscht das n-te Bit von links und permutierst diese Bitfolge durch. Dann löscht du das n+1-te Bit von links und permutierst erneut.

Damit ist das Problem nicht gelöst. Durch die Permutationen ergeben sich
unterschiedliche Anzahlen von einsen. Aber immerhin ein Versuch, auch wenn
nach 10 sekunden nachdenken klar ist, dass das so nicht klappt...

Man braucht keine 10 Sekunden um darauf zu kommen, das Permutarerereres Lösung funktioniert, wenn man 'intelligent' permutiert.

Jester

Eine Permutation ändert per Definition nicht die Anzahl von Einsen. Nach kurzem Nachdenken ist auch klar, dass die Lösung tatsächlich klappt. (Kann sein, dass das für manche mehr als 10 Sekunden braucht ;))

Mit dem Löschen des n-ten Bit von links ist es noch nicht getan, guckst du hier:

X: gelöschtes Bit

00100110011 // 5 Einsen
X0100110011 // 5 Einsen
XX100110011 // 5 Einsen

Dann ist die Aufgabenstellung des OP für mein Verständnis nicht ausreichend genau beschrieben:

Hallo,
ich suche einen Algorithmus, mit dem ich Zahlen von n..0 durchgehen
kann ...

Wenn ich nämlich die Einsen permutiere, dann hüpfe ich quasi im dezimalen hin und her, das ist kein Durchgehen, im Sinne von n...0

MfG
D.P.

bst2

Auch Hallo,

durchlaufe doch einfach alle Werte, zähle die Einsen und füge die Zahl sortiert nach a) Anzahl der Einsen und b) der Zahl selber dann in einer verketteten Liste ein.

cu, Bernd

Müsste doch irgendwie so aussehen:

[01] Sei x die Ausgangszahl
[02] Sei count die länge von X in Binärdarstellung
[03] gib x aus
[04] solange count > 0
[05]   finde eine 1 in x
[06]   ersetze die 1 durch 0
[07]   solange permutationen möglich sind
[08]     gib x aus und permutiere x
[09]     gehe zu [07]
[10]   verringer count um 1
[11] gehe zu 3

muss natürlich gehe zu 04 heißen