Как найти лексикографически следующую перестановку

Алгоритм: Как найти следующую лексикографическую перестановку

Время на прочтение
3 мин

Количество просмотров 33K

image

Если кратко описать, что такое лексикографический порядок — это сортировка в алфавитном порядке. Т.е. последовательность символов — AAA → AAB → AAC → AAD → ……… → WWW — является отсортированной в алфавитном (или в нашем случае лексикографическом) порядке.

Представьте, что у Вас есть конечная последовательность символов, например 0, 1, 2, 5, 3, 3, 0 и Вам необходимо найти все возможные перестановки этих символов. Наиболее интуитивным, но и наибольшим по сложности, является рекурсивный алгоритм, когда мы выбираем первый символ из последовательности, далее рекурсивно выбираем второй, третий итд, до тех пор, пока все символы из последовательности не будет выбраны. Понятно, что сложность такого алгоритма — O(n!).

Но оказывается, что наиболее простой алгоритм генерации всех перестановок в лексикографическом порядке — это начать с наименьшей и многократно вычислять следующую перестановку на месте. Давайте посмотрим как это сделать.

Точно также, как при расчете следующего целочисленного значения, мы должны стараться увеличить правую часть последовательности и оставить левую часть неизменной.

В качестве примера возьмем вышеприведенную последовательность — (0, 1, 2, 5, 3, 3, 0). Чтобы получить последовательность выше оригинальной, достаточно переставить первый и второй элементе местами, но в этом нет необходимости, так как можно переставить второй и и третий и получив более близкую по возрастанию последовательность. что приведет нас к следующей более близкой перестановки итд.

Наиболее оптимальным алгоритмом в этом случае будет следующий:

  1. Прежде всего Вы должны найти наибольший не-увеличивающийся суффикс. В вышеприведенном примере это будет — (5, 3, 3, 0). Если Вы попробуете сделать любую перестановку в данной последовательности, то она не будет выше оригинальной.
    Стоит сказать, что найти данную последовательность вы можете за O(n) времени, просматривая последовательность слева направо.
  2. Следующий элемент от суффикса является точкой поворота. В нашем случае — это 2. Точка поворота будет всегда меньше первого элемента суффикса. Это значит, что в суффиксе обязательно будет элемент превышающий точку поворота и если мы поменяет точку поворота на наименьший элемента из суффикса, превышающий опорный элемент точки поворота — мы получим последовательность превышающую оригинальную — в нашем случает это будет — (0, 1, 3, 5, 3, 2, 0).
    Т.е. результатом этой операции будет минимально возможный по возрастанию префикс.
  3. И на последнем шаге мы должны отсортировать суффикс в порядке возрастания. Т.е. мы получим минимально возможный суффикс. В нашем примере это будет (0, 2, 3, 5) и вся последовательность будет выглядеть как (0, 1, 3, 0, 2, 3, 5).

Это значение и будет следующей лексикографической перестановкой.

image

Что касается практического применения алгоритма, то за все время моей работы он мне ни разу не понадобился, но на интервью в Uber посчитали иначе :))

Для простоты весь код будет написан на Go и думаю никому не составить труда перевести его на любой другой язык программирования.

Большое спасибо PYXRU и 646f67, что ткнули меня носом в возможную оптимизацию алгоритма — произвести расчет перестановки за линейную сложность просто сделав reverse суффикса. 

func NextPermutationAlgorithm(w string) string {

 l := len(w)
	b := []byte(w)
	r := "no answer"

	for i:=l-1; i>0 ; i--{
		if b[i-1] < b[i] {
			pivot := i
			for j := pivot; j < l; j++ {
				if b[j] <= b[pivot] && b[i-1] < b[j] {
					pivot = j
				}
			}

			b[i-1], b[pivot] = b[pivot], b[i-1]

			for j := l-1; i < j; i, j = i+1, j-1 {
				b[i], b[j] = b[j], b[i]
			}

			r = string(b)
			break
		}
	}

	return r
}
Источник

All the permutations of a word when arranged in a dictionary, the order of words so obtained is called lexicographical order. in Simple words, it is the one that has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.

lexicographically is nothing but the greater permutation of it. 

For reference: a b c d e f g h i j k l m n o p q r s t u v w x y z

For example, lexicographically next permutation of “gfg” is “ggf” and the next permutation of “acb” is “bac”. 
Note: In some cases, the next lexicographically greater word might not exist, e.g, “aaa” and “edcba”. 

In C++, there is a specific function that saves us from a lot of code. It’s in the file #include <algorithm>. The function is next_permutation(a.begin(), a.end()). 
It returns ‘true’ if the function could rearrange the object as a lexicographically greater permutation. Otherwise, the function returns ‘false’.

Example:

CPP

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

    string s = { "gfg" };

    bool val

        = next_permutation(s.begin(),

                        s.end());

    if (val == false)

        cout << "No Word Possible"

            << endl;

    else

        cout << s << endl;

    return 0;

}

Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1), as constant extra space is used.

The same program can also be implemented without using STL. Below is the code snippet for the same. 

The Idea is Based on the Following Facts: 

  1. A sequence sorted in descending order does not have the next permutation. For example “edcba” does not have the next permutation.
  2. For a sequence that is not sorted in descending order for example “abedc”, we can follow these steps.  
    • a) Traverse from the right and find the first item that is not following the ascending order. For example in “abedc”, the character ‘b’ does not follow the ascending order.
    • b) Swap the found character with the closest greater (or smallest greater) element on the right side of it. In the case of “abedc”, we have ‘c’ as the closest greater element. After swapping ‘b’ and ‘c’, the string becomes “acedb”.
    • c) After swapping, reverse the string after the position of the character found in step a. After reversing the substring “edb” of “acedb”, we get “acbde” which is the required next permutation. 

Optimizations in steps b) and c) 
a) Since the sequence is sorted in decreasing order, we can use binary search to find the closest greater element. 

c) Since the sequence is already sorted in decreasing order (even after swapping as we swapped with the closest greater), we can get the sequence sorted (in increasing order) after reversing it. 

CPP

#include <iostream>

using namespace std;

void swap(char* a, char* b)

{

    if (*a == *b)

        return;

    *a ^= *b;

    *b ^= *a;

    *a ^= *b;

}

void rev(string& s, int l, int r)

{

    while (l < r)

        swap(&s[l++], &s[r--]);

}

int bsearch(string& s, int l, int r, int key)

{

    int index = -1;

    while (l <= r) {

        int mid = l + (r - l) / 2;

        if (s[mid] <= key)

            r = mid - 1;

        else {

            l = mid + 1;

            if (index == -1 || s[index] >= s[mid])

                index = mid;

        }

    }

    return index;

}

bool nextpermutation(string& s)

{

    int len = s.length(), i = len - 2;

    while (i >= 0 && s[i] >= s[i + 1])

        --i;

    if (i < 0)

        return false;

    else {

        int index = bsearch(s, i + 1, len - 1, s[i]);

        swap(&s[i], &s[index]);

        rev(s, i + 1, len - 1);

        return true;

    }

}

int main()

{

    string s = { "gfg" };

    bool val = nextpermutation(s);

    if (val == false)

        cout << "No Word Possible" << endl;

    else

        cout << s << endl;

    return 0;

}

Java

import java.io.*;

public class Main {

public static char[] nextPermutation(String s) {

    char[] arr = s.toCharArray();

    int n = arr.length;

    int i = n - 2;

    while (i >= 0 && arr[i] >= arr[i+1]) {

        i--;

    }

    if (i < 0) {

      String st = "No next Permutation possible";

      char[] ar = st.toCharArray();

        return ar;

    }

    int j = n - 1;

    while (j >= 0 && arr[j] <= arr[i]) {

        j--;

    }

    swap(arr, i, j);

    rev(arr, i+1, n-1);

    return arr;

}

private static void swap(char[] arr, int i, int j) {

    char temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

}

private static void rev(char[] arr, int start, int end) {

    while (start < end) {

        swap(arr, start, end);

        start++;

        end--;

    }

}

public static void main(String[] args)

    {

        String str2 = "gfg"; 

        System.out.println(nextPermutation(str2));

    }

}

Python3

def next_permutation(s: str) -> str:

    arr = list(s)

    n = len(arr)

    i = n - 2

    while i >= 0 and arr[i] >= arr[i+1]:

        i -= 1

    if i < 0:

        return "No next Permutation possible"

    j = n - 1

    while j >= 0 and arr[j] <= arr[i]:

        j -= 1

    arr[i], arr[j] = arr[j], arr[i]

    rev(arr, i+1, n-1)

    return ''.join(arr)

def rev(arr: list, start: int, end: int) -> None:

    while start < end:

        swap(arr, start, end)

        start += 1

        end -= 1

def swap(arr: list, i: int, j: int) -> None:

    temp = arr[i]

    arr[i] = arr[j]

    arr[j] = temp

if __name__ == '__main__':

    s = "gfg"

    print(next_permutation(s))

C#

using System;

class GFG {

    public static char[] NextPermutation(string s) {

        char[] arr = s.ToCharArray();

        int n = arr.Length;

        int i = n - 2;

        while (i >= 0 && arr[i] >= arr[i+1]) {

            i--;

        }

        if (i < 0) {

            string st = "No next Permutation possible";

            char[] ar = st.ToCharArray();

            return ar;

        }

        int j = n - 1;

        while (j >= 0 && arr[j] <= arr[i]) {

            j--;

        }

        Swap(arr, i, j);

        Reverse(arr, i+1, n-1);

        return arr;

    }

    private static void Swap(char[] arr, int i, int j) {

        char temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    private static void Reverse(char[] arr, int start, int end) {

        while (start < end) {

            Swap(arr, start, end);

            start++;

            end--;

        }

    }

    public static void Main(string[] args) {

        string str2 = "gfg"; 

        Console.WriteLine(NextPermutation(str2));

    }

}

Javascript

function next_permutation(s) {

    let arr = Array.from(s);

    let n = arr.length;

    let i = n - 2;

    while (i >= 0 && arr[i] >= arr[i+1]) {

        i--;

    }

    if (i < 0) {

        return "No next Permutation possible";

    }

    let j = n - 1;

    while (j >= 0 && arr[j] <= arr[i]) {

        j--;

    }

    let temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

    rev(arr, i+1, n-1);

    return arr.join('');

}

function rev(arr, start, end) {

    while (start < end) {

        swap(arr, start, end);

        start++;

        end--;

    }

}

function swap(arr, i, j) {

    let temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

}

let s = "gfg";

console.log(next_permutation(s));

Time Complexity:

  1. In the worst case, the first step of next_permutation takes O(n) time.
  2. The binary search takes O(log n) time.
  3. The reverse takes O(n) time.

Overall time complexity is O(n). Where n is the length of the string. 
Auxiliary Space is O(1), because no extra space is used.

This article is contributed by Harshit Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article on write.geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Last Updated :
06 Apr, 2023

Like Article

Save Article

Источник

Для заданной строки найти все ее лексикографически следующие перестановки.

Слова расположены в том же порядке в лексикографическом порядке, в каком они предположительно появляются в словаре. Например, лексикографически следующая перестановка строки ABCD является ABDC, для строки ABDC является ACBD, а для строки ACBD является ACDB.

Потренируйтесь в этой проблеме

 
Простым решением было бы использовать std::next_permutation который генерирует следующую большую лексикографическую перестановку строки. Если функция может определить следующую более высокую перестановку, она переставляет элементы и возвращает значение true. Если это невозможно (поскольку это уже максимально возможная перестановка), он переставляет элементы в соответствии с первой перестановкой и возвращает false.

Реализацию можно увидеть ниже на C++:

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

#include <iostream>

#include <algorithm>

using namespace std;

// Функция для поиска всех лексикографически следующих перестановок

// строка с использованием `std::next_permutation`

void permutations(string str)

{

    // базовый вариант

    if (str.length() == 0) {

        return;

    }

    while (1)

    {

        // печатаем текущую перестановку

        cout << str << » «;

        // найти следующую лексикографически упорядоченную перестановку

        if (!next_permutation(str.begin(), str.end())) {

            break;

        }

    }

}

int main()

{

    string str = «BADC»;

    permutations(str);

    return 0;

}

Скачать  Выполнить код

результат:

BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

 
Мы также можем реализовать собственные next_permutation() функция. Следующий алгоритм генерирует следующую перестановку лексикографически после данной перестановки. Это изменяет перестановку на месте.

  • Найдите самый большой индекс i такой, что str[i-1] меньше чем str[i].
  • Вернуть ложь, если i является первым индексом строки, что означает, что мы уже находимся в максимально возможной перестановке, т. е. строка отсортирована в порядке убывания. Если i не является первым индексом строки, тогда подстрока str[i…n) сортируется по убыванию, т. str[i-1] < str[i] >= str[i+1] >= str[i+2] >= … >= str[n-1].
  • Найдите самый высокий индекс j справа от указателя i такой, что str[j] больше, чем str[i-1] и поменять местами символ по индексу i-1 с индексом j.
  • Обратная подстрока str[i…n) и вернуть истину.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

#include <iostream>

#include <algorithm>

using namespace std;

// Функция для поиска следующих лексикографически перестановок строки.

// Возвращает true, если строка может быть переупорядочена как лексикографически

// большая перестановка; в противном случае возвращается ложь.

bool next_permutation(string &str, int n)

{

    // найти наибольший индекс `i`, такой, что `str[i-1]` меньше, чем `str[i]`

    int i = n — 1;

    while (str[i — 1] >= str[i])

    {

        // если `i` это первый индекс строки, это значит, что мы уже

        // при максимально возможной перестановке, т.е. строка отсортирована в

        // в порядке убывания

        if (—i == 0) {

            return false;

        }

    }

    /* Если мы доходим до этого места, подстрока `str[i…n)` сортируется в порядке убывания

       т. е. str[i-1] < str[i] >= str[i+1] >= str[i+2] >= … >= str[n-1] */

    // найти наибольший индекс `j` справа от индекса `i` такой, что

    // str[j] > str[i-1]

    int j = n — 1;

    while (j > i && str[j] <= str[i — 1]) {

        j—;

    }

    // поменять местами символ с индексом `i-1` на индекс `j`

    swap(str[i — 1], str[j]);

    // перевернуть подстроку `str[i…n)` и вернуть true

    reverse (str.begin() + i, str.end());

    return true;

}

// Функция для поиска всех лексикографически следующих перестановок строки

void permutations(string str)

{

    int n = str.length();

    // базовый вариант

    if (n == 0) {

        return;

    }

    // базовый вариант

    if (n == 1) {

        cout << str;

        return;

    }

    while (1)

    {

        // печатаем текущую перестановку

        cout << str << » «;

        // найти следующую лексикографически упорядоченную перестановку

        if (!next_permutation(str, str.length())) {

            break;

        }

    }

}

int main()

{

    string str = «BADC»;

    permutations(str);

    return 0;

}

Скачать  Выполнить код

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

import java.util.Arrays;

class Main

{

    private static void swap(char[] chars, int i, int j)

    {

        char ch = chars[i];

        chars[i] = chars[j];

        chars[j] = ch;

    }

    private static void reverse(char[] chars, int start)

    {

        for (int i = start, j = chars.length — 1; i < j; i++, j—) {

            swap(chars, i, j);

        }

    }

    // Функция для поиска следующих лексикографически перестановок строки.

    // Возвращает true, если строка может быть переупорядочена как лексикографически

    // большая перестановка; в противном случае возвращается ложь.

    public static boolean next_permutation(char[] chars)

    {

        // найти наибольший индекс `i`, такой, что `chars[i-1]` меньше, чем `chars[i]`

        int i = chars.length — 1;

        while (chars[i — 1] >= chars[i])

        {

            // если `i` это первый индекс строки, это значит, что мы уже

            // при максимально возможной перестановке, т.е. строка отсортирована в

            // в порядке убывания

            if (—i == 0) {

                return false;

            }

        }

        /*

            если мы достигнем этого места, подстрока `chars[i…n)` будет отсортирована в порядке убывания

            т.е. chars[i-1] < chars[i] >= chars[i+1] >= chars[i+2] >= … >= chars[n-1]

        */

        // найти наибольший индекс `j` справа от индекса `i` такой, что

        // chars[j] > chars[i-1]

        int j = chars.length — 1;

        while (j > i && chars[j] <= chars[i — 1]) {

            j—;

        }

        // поменять местами символ с индексом `i-1` на индекс `j`

        swap(chars, i — 1, j);

        // перевернуть подстроку `chars[i…n)` и вернуть true

        reverse(chars, i);

        return true;

    }

    // Функция для поиска всех лексикографически следующих перестановок строки

    public static void permutations(String str)

    {

        // базовый вариант

        if (str == null || str.length() == 0) {

            return;

        }

        // базовый вариант

        if (str.length() == 1) {

            System.out.print(str);

            return;

        }

        // преобразовать строку в массив символов

        char[] chars = str.toCharArray();

        while (true)

        {

            // печатаем текущую перестановку

            System.out.print(new String(chars) + » «);

            // найти следующую лексикографически упорядоченную перестановку

            if (!next_permutation(chars)) {

                break;

            }

        }

    }

    public static void main(String[] args)

    {

        String str = «BADC»;

        permutations(str);

    }

}

Скачать  Выполнить код

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

def swap(chars, i, j):

    ch = chars[i]

    chars[i] = chars[j]

    chars[j] = ch

def reverse(chars, start):

    (i, j) = (start, len(chars) — 1)

    while i < j:

        swap(chars, i, j)

        i = i + 1

        j = j — 1

# Функция поиска лексикографически следующих перестановок строки.

# Возвращает истину, если строка может быть переупорядочена как лексикографически

# большая перестановка; в противном случае возвращается ложь.

def next_permutation(chars):

    # найти наибольший индекс `i`, такой, что `chars[i-1]` меньше, чем `chars[i]`

    i = len(chars) — 1

    while chars[i — 1] >= chars[i]:

        #, если `i` является первым индексом строки, это означает, что мы уже

        # при максимально возможной перестановке, т. е. строка отсортирована в

        # в порядке убывания

        i = i — 1

        if i == 0:

            return False

    »’ if we reach here, the substring `chars[i…n)` is sorted in descending order;

        i.e., chars[i-1] < chars[i] >= chars[i+1] >= chars[i+2] >= … >= chars[n-1] »’

    # найти наибольший индекс `j` справа от индекса `i` такой, что

    # `chars[j] > chars[i-1]`

    j = len(chars) — 1

    while j > i and chars[j] <= chars[i — 1]:

        j = j — 1

    # поменять местами символ с индексом `i-1` на индекс `j`

    swap(chars, i — 1, j)

    # перевернуть подстроку `chars[i…n)` и вернуть true

    reverse(chars, i)

    return True

# Функция для поиска всех лексикографически следующих перестановок строки

def permutations(s):

    # Базовый вариант

    if not s:

        return

    # Базовый вариант

    if len(s) == 1:

        print(s)

        return

    # преобразовать строку в список

    chars = list(s)

    while True:

        # распечатать текущую перестановку

        print(».join(chars), end=‘ ‘)

        # найти следующую лексикографически упорядоченную перестановку

        if not next_permutation(chars):

            break

if __name__ == ‘__main__’:

    s = ‘BADC’

    permutations(s)

Скачать  Выполнить код

Output:

 
BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

Временная сложность приведенных выше решений в наихудшем случае равна O(n.n!) как есть n! перестановки для строки длины n, и каждая перестановка занимает O(n) время. Худший случай возникает, когда строка содержит все отдельные элементы.

 
Обратите внимание, что приведенное выше решение может обрабатывать строки, содержащие повторяющиеся символы, и не будет печатать повторяющиеся перестановки.

 
Также см:

Найти все лексикографически предыдущие перестановки строки

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования :)

Источник

Содержание

  • 1 Алгоритм
  • 2 Специализация алгоритма для генерации следующего битового вектора
    • 2.1 Пример работы
  • 3 Специализация алгоритма для генерации следующей перестановки
    • 3.1 Пример работы
  • 4 Специализация алгоритма для генерации следующей мультиперестановки
    • 4.1 Пример работы
  • 5 Специализация алгоритма для генерации следующего сочетания
    • 5.1 Пример работы
  • 6 Специализация алгоритма для генерации следующего разбиения на слагаемые
    • 6.1 Пример работы
  • 7 Специализация алгоритма для генерации следующего разбиения на подмножества
    • 7.1 Пример работы
  • 8 См.также
  • 9 Источники информации

Алгоритм

Объект называется следующим за , если и не найдется такого , что .

Отсюда понятен алгоритм:

  • находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта ,
  • к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило ),
  • дописываем минимальный возможный хвост.

По построению получаем, что — минимально возможный.

Специализация алгоритма для генерации следующего битового вектора

  • Находим минимальный суффикс, в котором есть , его можно увеличить, не меняя оставшейся части
  • Вместо записываем
  • Дописываем минимально возможный хвост из нулей
int[] nextVector(int[] a): //  — длина вектора
  while (n >= 0) and (a[n] != 0)
      a[n] = 0
      n--
  if n == -1
    return null
  a[n] = 1
  return a

Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.

Пример работы

0 1 0 1 1 исходный битовый вектор
^ начинаем идти с конца
0 1 0 0 0 пока элементы равны 1, заменяем их на 0
0 1 1 0 0 меняем первый не удовлетворяющий условию цикла элемент на 1
0 1 1 0 0 следующий битовый вектор

Специализация алгоритма для генерации следующей перестановки

  • Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
  • Меняем его с минимальным элементом, большим нашего, стоящим правее
  • Перевернем правую часть
int[] nextPermutation(int[] a): //  — длина перестановки
  for i = n - 2 downto 0
    if a[i] < a[i + 1]
      min = i + 1;
      for j = i + 1 to n - 1
        if (a[j] < a[min]) and (a[j] > a[i])
          min = j
      swap(a[i], a[min])
      reverse(a, i + 1, n - 1)
      return a
  return null

Пример работы

1 3 2 5 4 исходная перестановка
^ находим элемент, нарушающий убывающую последовательность
^ минимальный элемент больше нашего
1 3 4 5 2 меняем их местами
1 3 4 2 5 разворачивам правую часть
1 3 4 2 5 следующая перестановка

Специализация алгоритма для генерации следующей мультиперестановки

  • Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
  • Меняем его с минимальным элементом, большим нашего, стоящим правее.
  • Переворачиваем правую часть.
int[] nextMultiperm(int[] b):  //  — длина мультиперестановки
    i = n - 2
    while (i >= 0) and (b[i] >= b[i + 1]) 
      i--
    if i >= 0 
      j = i + 1
      while (j < n - 1) and (b[j + 1] > b[i]) 
        j++
      swap(b[i] , b[j])
      reverse(b, i + 1, n - 1)
      return b
    else
      return null

Пример работы

1 2 3 1 2 3 Исходная перестановка.
^ Находим элемент, нарушающий убывающую последовательность.
^ Минимальный элемент больше нашего.
1 2 3 1 3 2 Меняем их местами.
1 2 3 1 3 2 Следующая мультиперестановка.

Специализация алгоритма для генерации следующего сочетания

  • Добавим в конец массива с сочетанием – максимальный элемент.
  • Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на и больше.
  • Увеличим найденный элемент на , и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
int[] nextChoose(int[] a, int n, int k): //  — параметры сочетания
  for i = 0 to k - 1 
    b[i] = a[i]
  b[k] = n + 1
  i = k - 1
  while (i >= 0) and (b[i + 1] - b[i] < 2) 
    i--
  if i >= 0 
     b[i]++
     for j = i + 1 to k - 1 
       b[j] = b[j - 1] + 1
     for i = 0 to k - 1 
       a[i] = b[i]
     return a
  else
    return null

Пример работы

1 2 5 6 7 Дописываем 7 в конец сочетания.
1 2 5 6 7
^ Находим элемент i, a[i + 1] — a[ i ] >= 2
1 3 5 6 7 Увеличиваем его на 1.
1 3 4 5 6 Дописываем минимальный хвост.
1 3 4 5 Следующее сочетание.

Специализация алгоритма для генерации следующего разбиения на слагаемые

Рассматриваемый алгоритм находит следующее разбиение на слагаемые, при этом разбиение упорядоченно по возрастанию.

  • Увеличим предпоследнее слагаемое на , уменьшим последнее слагаемое на .
    • Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
    • Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое на два слагаемых и таких, что равно предпоследнему слагаемому, а . Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.

//  — список, содержащий разбиение данного числа — его размер 
list<int>  nextPartition(list<int> b): 
   b[b.size - 1]--
   b[b.size - 2]++
   if b[b.size - 2] > b[b.size - 1] 
      b[b.size - 2] += b[b.size - 1]
      b.remove(b.size - 1)
   else
     while b[b.size - 2] * 2 <= b[b.size - 1] 
       b.add(b[b.size - 1] - b[b.size - 2])
       b[b.size - 2] = b[b.size - 3]
   return b

Пример работы

1 1 7 Прибавим 1 + 1, вычтем 7 — 1.
1 2 6 Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4
1 2 2 4
1 2 2 2 2
1 2 2 2 2 Следующее разбиение на слагаемые числа 9.
1 4 5 Прибавим 4 + 1, вычтем 5 — 1.
1 5 4 Проверяем: 5 > 4, значит прибавим к 5 + 4.
1 9 4 Удалим последний элемент.
1 9 Следующее разбиение на слагаемые числа 10.

Специализация алгоритма для генерации следующего разбиения на подмножества

Рассмотрим множество первых n натуральных чисел:

Упорядочим все разбиения на множества лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество лексикографически меньше подмножества , если верно одно из следующих условий:

  • существует такое, что , , для всех если и только если , и существует такое что ;
  • и для всех и .

Разбиения упорядочены лексикографически следующим образом. Разбиение лексикографически меньше разбиения если существует такое , что .

Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:

  • Будем хранить подмножества в списке списков, например, разбиение будет выглядеть так:
  • Будем поддерживать массив удалённых элементов — элементы, которые затем нужно будет вернуть в разбиение.
  • Двигаясь снизу вверх будем рассматривать подмножества.
    • Если мы можем дописать в текущее подмножество минимальный элемент из удалённых, то мы нашли следующее разбиение и нужно завершить цикл.
    • Если дописать не можем, значит, либо нужно укоротить и заменить какой-то элемент в текущем подмножестве, либо перейти к следующему подмножеству. Будем идти справа налево и рассматривать элементы:
      • Если мы можем заменить текущий элемент минимальным удалённым — мы нашли следующее разбиение, завершаем оба цикла и выполняем алгоритм дальше. Стоит отметить, что нельзя перезаписывать последний элемент в подмножестве, иначе мы не сможем дописать минимальный хвост после этого подмножества — в удалённых будет элемент меньше текущего и мы не сможем выписать удаленные элементы так, чтобы получилось корректное разбиение.
      • Если заменить текущий элемент каким-то из удалённых нельзя, то следует удалить и этот.
  • Допишем лексикографически минимальный хвост подмножеств из оставшихся удалённых элементов.
list<list<int>> nextSetPartition(list<list<int>> a):
  used = list<int>
  // a — список, содержащий подмножества
  // used — список, в котором мы храним удаленные элементы
  fl = false
  for i = a.size - 1 downto 0
    if (used.size != 0) and (max(used) > a[i][-1])   // в удалённых есть хотя бы один элемент, который мы можем добавить в конец.
      m = минимум из used строго больше a[i][-1]
      a[i].add(m)   // добавляем
      used.remove(m)
      break
    for j = a[i].size - 1 downto 0
      if (used.size != 0) and (j != 0) and (max(used) > a[i][j])   // если можем заменить элемент, другим элементом из списка used и он не последний
        m = минимум из used строго больше a[i][j]
        old = a[i][j]
        a[i][j] = m   // заменяем
        used.remove(m)
        used.add(old)
        fl = true
        break
      else
        used.add(a[i][-1])
        a[i].pop()
        if a[i].size == 0
          a.pop()
     if fl 
       break
  // далее выведем все удалённые, которые не выбрали
  sort(used)
  for i = 0 to used.size - 1
     a.add(list<int>(used[i]))   // добавляем лексикографически минимальных хвост
  return a

Пример работы

Рассмотрим следующее разбиение:

1 Шаг:

1 2 3
4 5
^ Удалили элемент 5.
Удалённые элементы

2 Шаг:

1 2 3
4
^ Удалили элемент 4. Так как он является последним в подмножестве, то мы не можем заменить его на другой.
5 Удалённые элементы

3 Шаг:

1 2 3 4
^ Дополнили первое подмножество элементом 4
5 Удалённые элементы

4 Шаг:

1 2 3 4
5 Дописали лексикографически минимальный хвост
Удалённые элементы

См.также

  • Получение предыдущего объекта
  • Получение объекта по номеру
  • Получение номера по объекту

Источники информации

  • Визуализатор перестановок
  • Пример компактного кода для перестановок (С++)
Источник

Студворк — интернет-сервис помощи студентам

Типичная задачка с лексикографической сортировкой. Даётся число N и перестановка (порядок чисел от 1 до N). Нужно найти следующую перестановку в лексикографическом порядке (пример, из после последовательности «N, N-1…3,2,1» будет идти «1,2,3…N»)
Я тут пытался что-то накалякать… Но я прям начинающий программист, у меня вышло что-то такое:

C++ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <cmath>
using namespace std;
 
int main(int argc, char *argv[])
{
    int N=0;
    cin>>N;
    int num[N];
    
    for (int i=0; i<N; i++)
    {
        cin>>num[i];
    }
 
    int buff=0;
    for (int j=N-2; j>=0; j--)
    {
        if (num[j]<num[j+1])
        {
            cout<<num[j]<<"<"<<num[j+1]<<endl;
            for(int l=N-1; l>j; l--)
            {
                if (num[l]>num[j])
                {
                    cout<<"l="<<num[l]<<endl;
                    buff=num[l];
                    num[l]=num[j];
                    num[j]=buff;
                    cout<<num[j]<<", "<<num[l]<<endl;
                    for (int k=0; k<ceil((N-j)/2); k++)
                    {
                        buff=num[N-k-1];
                        num[N-k-1]=num[j+k+1];
                        num[j+k+1]=buff;
                    }
                    break;
                }
            }
            break;
        }
    }
    
    for (int g=0; g<N; g++)
    {
        cout<<num[g]<<" ";
    }
}

Удачи вам разобраться в моём коде:З

Источник

Понравилась статья? Поделить с друзьями:
  • Как найти друзей вк по списку контактов
  • Личный кабинет билайн как найти пароль
  • Скачать как найти телефон самсунг
  • Как на браузере опера найти сохраненные пароли
  • Как найти радиус окружности на клетчатой бумаге