Bijektion gesucht

Neue Frage »

Mathematiker9998 Auf diesen Beitrag antworten »
Bijektion gesucht
Meine Frage:
Hallo,

ich habe folgendes Problem:

Gegeben sind alle Binaerzahlen mit n Stellen und einer beliebigen, aber festen Anzahl k an Einsen (z.B. für n=4 und k=2: 1001, 1100, 0011, 0110, 1010, 0101). Bezeichne diese Mengen als M(n;k). Ich suche nun eine Bijektion zwischen den M(n;k) und den natürlichen Zahlen (z.B. für n=4 und k=2: 0, 1, 2, 3, 4, 5). Ich möchte die Elemente der Mengen M(n;k) also durchnummerieren. Das ganze soll in ein Programm umgesetzt werden, daher wäre es sinnvoll eine (kompakte!) Zuordnungsvorschrift anzugeben.

Meine Ideen:
Leider habe ich keine Idee, ich hab schon versucht mit Modulo-Tabellen zu arbeiten, bin daran aber gescheitert.
HAL 9000 Auf diesen Beitrag antworten »

Nun, es ist . "Durchnummerieren" ist schwierig, aber alle Varianten algorithmisch ausgeben ist nicht so schwer, im Pseudocode
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
M(n, k, string)
{
   if (n == 0)
   {
       print(string);
   }
   else
   {
       if (k < n)
       {
           M(n-1, k, string + "0");
       }
       if (k > 0)
       {
           M(n-1, k-1, string + "1");
       }
   }
}

Aufruf dieser rekursiven Funktion mit M(n,k,""); erlaubt ist natürlich nur .
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »