Iterate binary numbers with the same number of units (or zeros) in random order

Question

I need to generate binary numbers with the same number of units (or zeros) in random order.
Does anyone know an efficient algorithm for fixed-length binary numbers? Example for 2 and 4 digits (only for clearer):

1100
1010
1001
0110
0101
0011

UPDATE Random without repetition is significant. It requires a sequence of binary numbers, not one permutation.

Answer 1

-, , , , , Shuffle Fisher-Yates. ( ), , n , , .

, . (C .)

1.

( ) - , , . , , . ( " ", , 1, 1 .) , , , . , n , . (, , n 4 k 2, 6 , 6! (720) , 4! (24) -. , .)

. n = 6, k = 3: ( . , - SO , .)

111000   010110   100011   010101
101100   001110   010011   001101
011100   101010   001011   101001
110100   011010   000111   011001
100110   110010   100101   110001

, @JasonBoubin - , - . Frank Ruskey ( 5.7 . 130). , 0, .

2.

"" , - ( [0, n choose k)), , .

- (LCG). LCG - xi = (a * xi-1 + c) mod m. m 2, a mod 4 1, c mod 2 1, 2 ^m . [0, n choose k), m 2, , . ( .)

, , , n choose k n-1 choose k, 0 n-1 choose k-1, a 1. , ^th:

• if i < n-1 choose k 0, ^th n-1 k ;
• 1, n-1 choose k n-1 k-1 .

.

LCG , , . , a c , . ( , .) , - . , , , . ( 1UL<<n ).

C , . :

  row
index
 [ 0]   1
 [ 1]   1 1
 [ 3]   1 2 1
 [ 6]   1 3 3 1
 [10]   1 4 6 4 1

, binom(n, k) n(n+1)/2 + k, , binom(n-1, k) n binom(n-1, k-1) n+1. , , , k , n. , , k == n k == 0, , 0, . , 0 n k n-k , k , n- 2 ^k -1. , 0, , binom(n-1, k) binom(n-1, k-1) .

C-

void gray_combs(int n, int k) {
  /* bit[i] is the ith shuffled bit */
  uint32_t bit[n+1];
  {
    uint32_t mask = 1;
    for (int i = 0; i < n; ++i, mask <<= 1)
      bit[i] = mask;
    bit[n] = 0;
    shuffle(bit, n);
  }

  /* comb[i] for 0 <= i < k is the index of the ith bit
   * in the current combination. comb[k] is a sentinel. */
  int comb[k + 1];
  for (int i = 0; i < k; ++i) comb[i] = i;
  comb[k] = n;

  /* Initial word has the first k (shuffled) bits set */
  uint32_t word = 0;
  for (int i = 0; i < k; ++i) word |= bit[i];

  /* Now iterate over all combinations */
  int j = k - 1; /* See Ruskey for meaning of j */
  do {
    handle(word, n);
    if (j < 0) {
      word ^= bit[comb[0]] | bit[comb[0] - 1];
      if (--comb[0] == 0) j += 2;
    }
    else if (comb[j + 1] == comb[j] + 1) {
      word ^= bit[comb[j + 1]] | bit[j];
      comb[j + 1] = comb[j]; comb[j] = j;
      if (comb[j + 1] == comb[j] + 1) j += 2;
    }
    else if (j > 0) {
      word ^= bit[comb[j - 1]] | bit[comb[j] + 1];
      comb[j - 1] = comb[j]; ++comb[j];
      j -= 2;
    }
    else {
      word ^= bit[comb[j]] | bit[comb[j] + 1];
      ++comb[j];
    }
  } while (comb[k] == n);
}

LCG

static const uint32_t* binom(unsigned n, unsigned k) {
  static const uint32_t b[] = {
    1,
    1, 1,
    1, 2, 1,
    1, 3, 3, 1,
    1, 4, 6, 4, 1,
    1, 5, 10, 10, 5, 1,
    1, 6, 15, 20, 15, 6, 1,
    // ... elided for space
  };
  return &b[n * (n + 1) / 2 + k];
}

static uint32_t enumerate(const uint32_t* b, uint32_t r, unsigned n, unsigned k) {
  uint32_t rv = 0;
  while (r) {
    do {
      b -= n;
      --n;
    } while (r < *b);
    r -= *b;
    --b;
    --k;
    rv |= 1UL << n;
  }
  return rv + (1UL << k) - 1;
}

static bool lcg_combs(unsigned n, unsigned k) {
  const uint32_t* b = binom(n, k);
  uint32_t count = *b;
  uint32_t m = 1; while (m < count) m <<= 1;
  uint32_t a = 4 * randrange(1, m / 4) + 1;
  uint32_t c = 2 * randrange(0, m / 2) + 1;
  uint32_t x = randrange(0, m);
  while (count--) {
    do
      x = (a * x + c) & (m - 1);
    while (x >= *b);
    handle(enumerate(b, x, n, k), n);
  }
  return true;
}

: randrange shuffle; . randrange(low, lim) [low, lim); shuffle(vec, n) vec n.

, handle(word, n) . , .

handle, , , gray_combs 150 , 40,116,600 28- 14 . lcg_combs 5.5 .

Answer 2

.

, , - (. ), , 16- ( ) - ( ):

uint permute(uint x) {
  x = bit_permute_step(x, 0x00005110, 1);  // Butterfly, stage 0
  x = bit_permute_step(x, 0x00000709, 4);  // Butterfly, stage 2
  x = bit_permute_step(x, 0x000000a1, 8);  // Butterfly, stage 3
  x = bit_permute_step(x, 0x00005404, 1);  // Butterfly, stage 0
  x = bit_permute_step(x, 0x00000231, 2);  // Butterfly, stage 1
  return x;
}

uint bit_permute_step(uint x, uint m, int shift) {
  uint t;
  t = ((x >> shift) ^ x) & m;
  x = (x ^ t) ^ (t << shift);
  return x;
}

:

uint i = (1u << k) - 1;
uint max = i << (wordsize - k);
do
{
    yield permute(i);
    i = nextPermutation(i);
} while (i != max);
yield permute(i); // for max

nextPermutation ,

uint nextPermutation(uint v) {
  uint t = (v | (v - 1)) + 1;
  uint w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
  return w;
}

- (, 0.. (wordize-1) ), ( programming.sirrida.de/calcperm.php), .

Answer 3

. ++:

#include<iostream>
#include<string>
#include<iostream>
void binaryPermutation(int ones, int digits, std::string current){
        if(digits <= 0 && ones <= 0){
                std::cout<<current<<std::endl;
        }
        else if(digits > 0){
                if(ones > 0){
                        binaryPermutation(ones-1, digits-1, current+"1");
                }
                binaryPermutation(ones, digits-1, current+"0");
        }
}
int main()
{
        binaryPermutation(2, 4, "");
        return 0;
}

: 1100 1010 1001 0110 0101 0011

, - , .

Answer 4

Python, ?

from itertools import permutations

fixed_length = 4
perms = [''.join(p) for p in permutations('11' + '0' * (fixed_length - 2))]
unique_perms = set(perms)

, int(num, 2).

, 0,021 .

Answer 5

, . n . .

, BINARY. LFSR.

LFSR is a simple method for iterating over all numbers. I think you can make some simple modifications for generations of fixed-size zeros with LFSR.