Как сгенерировать все перестановки множества, состоящие из `k```````````` в лексикографическом порядке?

Как сгенерировать все перестановки множества, состоящие из k0's и l1's в лексикографическом формате? Я ищу псевдокод или код на C++. Пример:Как сгенерировать все перестановки множества, состоящие из `k```````````` в лексикографическом порядке?

функция next_perm01 должна работать так: next_perm01(permutation_{i})=next_perm01(permutation_{i-1}) я нашел только способ генерации всех перестановок множества различных элементов.

источник

2013-03-01 Qbik

Это в Java, но вы можете рассматривать это как псевдо-код:

public static boolean nextPermutation (int [] permutation) 
{ 
    int l = permutation.length; 
    if (l < 2) return false; 
    else 
    { 
     int i = l - 1; 
     while (i >= 0 && permutation [i] == 0) 
      i--; 

     int j = 0; 
     while (i >= 0 && permutation [i] == 1) 
     { 
      i--; 
      j++; 
     } 

     if (i < 0) return false; 
     else 
     { 
      permutation [i] = 1; 

      Arrays.fill (permutation, i + 1, l - j + 1, 0); 
      Arrays.fill (permutation, l - j + 1, l, 1); 

      return true; 
     } 
    } 
} 

public static void main(String[] args) { 
    int [] permutation = new int [] {0, 0, 0, 1, 1, 1, 1}; 
    do 
    { 
     for (int i: permutation) 
      System.out.print(i); 
     System.out.println(); 
    } while (nextPermutation(permutation)); 
}

Выход для меня является:

источник

2013-03-01 14:30:34

Начните с наименьшим номером, который имеет l 1 в нем: (1 << l) - 1

Затем примените NextBitPermutation, пока не достигнете наибольшего числа, то есть lowest << k.

источник

2013-03-01 14:34:12 harold

Начните с перестановки k 0s, за которой следует l 1s. Повторите этот шаг, пока вы можете:

Найти крайний правый участок д 1s (Q > 0), которым предшествует 0 и с последующим г 0s (г > = 0). Замените все на 1, за которым следует (r + 1) 0s, за которым следует (q-1) 1s. Это будет ваша следующая перестановка.

источник

2013-03-01 14:42:20

Если я правильно понимаю, то общий алгоритм для строки может быть:

nextPermutation string = 
scan string from right to left 
replace first occurrence of "01" with "10" 
move all "1"'s that are on the right of the "01" to the string end* 
return replaced string

* Благодаря н.м. за то, что я указал на свою ошибку.

источник

2013-03-01 15:38:20

Как вы получаете '1001' от' 0011'? –

@ н.м. мой алгоритм будет идти от '0011' до' 0101'. почему вы хотите перейти на '1001' с' 0011'? –

Я не хочу, чтобы он переходил прямо с '0011' на' 1001', я хочу, чтобы он туда поехал. Будет ли это когда-нибудь? –

Generating All Permutations по D.E.Knuth

См Алгоритм L (лексикографический генерации перестановок) на начало первой главы

источник

2013-03-01 17:32:15 frankyym

Как сгенерировать все перестановки множества, состоящие из `k```````````` в лексикографическом порядке?

ответ

Смежные вопросы