Перестановка – это комбинация элементов из {\displaystyle{N}} разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все {\displaystyle{N}} элементов.
Задача: Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:
1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1
Перестановки без повторений
Количество перестановок для {\displaystyle{N}} различных элементов составляет {\displaystyle{N!}}.
Действительно:
- на первое место может быть помещен любой из {\displaystyle{N}} элементов (всего вариантов {\displaystyle{N}}),
- на вторую позицию может быть помещен любой из оставшихся {\displaystyle{(N-1)}} элементов (итого вариантов {\displaystyle{N \cdot (N-1)}}),
- если продолжить данную последовательность для всех {\displaystyle{N}} мест, то получим: {\displaystyle{N \cdot (N-1) \cdot (N-2) \cdot … \cdot 1}}, то есть всего {\displaystyle{N!}}перестановок.
Рассмотрим задачу получения всех перестановок чисел {\displaystyle{1…N}} (то есть последовательности длины {\displaystyle{N}}), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка {\displaystyle{1 \ 2 \ … \ N}}, а последней — {\displaystyle{N \ (N-1) \ … \ 1}}.
Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел.
Для получения каждой следующей перестановки необходимо выполнить следующие шаги:
- Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).
- Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.
- Поменять местами два полученных элемента.
- Теперь в части массива, которая размещена справа от позиции 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
#include <iostream>
using namespace std;
void swap(int* a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int* a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l < r)
swap(a, l++, r--);
return true;
}
void Print(int* a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int n, * a;
cout << "N = ";
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}
Перестановки с повторениями
Особого внимания заслуживает задача генерации перестановок {\displaystyle{N}} элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов {\displaystyle{n_1,\ n_2,\ …\ n_k}}, где элемент {\displaystyle{n_1}} повторяется {\displaystyle{r_1}} раз, {\displaystyle{n_2}} повторяется {\displaystyle{r_2}} раз и т.д.
При этом {\displaystyle{n_1 + n_2 + … + n_k = N}}.
Если мы будем считать все {\displaystyle{n_1 + n_2 + … + n_k}} элементов перестановки с повторениями различными, то всего различных вариантов перестановок {\displaystyle{(n_1 + n_2 + … + n_k)!}}.
Однако среди этих перестановок не все различны. В самом деле, все {\displaystyle{r_1}} элементов {\displaystyle{n_1}} мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы {\displaystyle{n_2}}, {\displaystyle{n_3}} и т. д. В итоге имеем {\displaystyle{r_1!}} вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов {\displaystyle{n_1}}.
Таким образом, всякая перестановка может быть записана {\displaystyle{r_1! \cdot r_2! \cdot … \cdot r_k!}} способами. Следовательно, число различных перестановок с повторениями равно
{\displaystyle{P=\frac {n!}{r_1! \cdot r_2! \cdot … \cdot r_k!}}}
Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a.
Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()).
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
#include <iostream>
using namespace std;
void swap(int* a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int* a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l < r)
swap(a, l++, r--);
return true;
}
void Print(int* a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int n, * a;
cout << "N = ";
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a[1] = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}Результат работы приведенного выше алгоритма:
Елена, Вы так все понятно и доступно объясняете! По поводу темы перестановок элементов, Вам случайно не известен метод эффективного порождения перестановок. Никак не пойму его смысл, а уж тем более как его можно реализовать в код. Могли бы Вы помочь с этим вопросом?
Roman Sechin
Здравствуйте, Елена! Подскажите, пожалуйста, что нужно изменить в алгоритме поиска перестановок с повторениями, если n1 + n2 + .. + nk = S (S != N)? Благодарю!
Найти все различные разложения S, и для каждого разложения найти перестановки.
как получить лексикографически максимальную исходную перестановку?
Насколько я понимаю, записать в обратном порядке
Добрый день! У меня задача: нужна одна перестановка после генерации рандомного массива, если подробно, то например задается массив [4 3 1 5 0], следующая перестановка по правилам будет [4 3 5 1 0] и на этом нужно остановиться. Не могли бы вы помочь?
Как выбирается нужная перестановка? Я бы нашла первую перестановку [4 3 1 0 5]
Сортировка массива?
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
using namespace std;
void swap(char *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(char *a, int k)
{
int j = k — 2;
while (j != -1 && a[j] >= a[j + 1]) j—;
if (j == -1)
return false; // больше перестановок нет
int n = k — 1;
while (a[j] >= a[n]) n—;
swap(a, j, n);
int l = j + 1, r = k — 1; // сортируем оставшуюся часть последовательности
while (l < r)
{
swap(a, l++, r—);
}
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int k;
std::cout << "k = ";
std::cin >> k;
char *a = new char[k + 1]{};
for (int i = 0; i < k; i++)
{
a[i] = 'a' + i;
}
std::cout << a << std::endl;
while (NextSet(a, k))
{
std::cout << a << std::endl;
}
return 0;
}
всё отлично, но мне нужна перестановка из введённого вручную набора элементов
В строчке 44 ввести вручную числа. Затем их отсортировать по возрастанию, после чего выполнить генерацию перестановок
Добрый вечер. Можете пожалуйста помочь с задачей?
Создать программу для дешифрации методом оптимизированного перебора записи действия сложения в девятом системе счисления: Anna + Luisa = Sussen, в котором одинаковые цифры обозначены одинаковыми буквами, а разные цифры обозначены разными буквами.
Очень надеюсь на Вашу помощь
Перебор — это вложенные циклы, где каждый параметр цикла отвечает за свою букву. 7 букв — значит, 7 циклов.
Поскольку система счисления 9-ричная, каждый цикл повторяется 9 раз.
А дальше формируем числа и сравниваем их.
Anna = a*1000+n*100+n*10+a;
Можешь отправить то что у тебя получилось?
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
#include <string>
#include <vector>
using namespace std;
void swap(int* a, int i, int j, vector<string>& vec)
{
int s = a[i];
string temp = vec[i];
a[i] = a[j];
vec[i] = vec[j];
a[j] = s;
vec[j] = temp;
}
bool NextSet(int* a, int n, vector<string>& vec)
{
int j = n — 2;
while (j != -1 && a[j] >= a[j + 1]) j—;
if (j == -1)
return false; // больше перестановок нет
int k = n — 1;
while (a[j] >= a[k]) k—;
swap(a, j, k, vec);
int l = j + 1, r = n — 1; // сортируем оставшуюся часть последовательности
while (l < r)
swap(a, l++, r—, vec);
return true;
}
void Print(int* a, int n, vector<string>& vec) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << vec[i] << " ";
cout << endl;
}
int main()
{
vector<string> vec = { "A", "B", "C", "D" };
setlocale(LC_ALL, "ru");
int n;
string temp;
cout << "Введите кол-во элементов: ";
cin >> n;
int* a = new int [n];
for (int i = 0; i < n; i++) {
a[i] = i+1;
}
cout << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (vec[i] == vec[j])
a[j] = a[i];
}
}
Print(a, n, vec);
while (NextSet(a, n, vec))
Print(a, n, vec);
delete a;
return 0;
}
Перестановки на PascalABC.net рекурсивно:
2
3
4
5
6
7
8
9
10
begin
if length(S1) > 1 then
for var i:=1 to length(S1) do Per(S0+S1[i],copy(S1,1,i-1) +
copy(S1,i+1,length(S1)))
else Writeln(S0+S1);
end;
begin
Per('','12345'); //S0 =0, S1 = Text
end.
Реализация на PascalABC
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
var n := 4; // Перестановки для n различных элементов без повторений
var a := new integer [n + 2]; //массив для перестановки
for var e := 1 to n do a[e] := e; //начальная перестановка a = 012..n0 (c нулями по краям)
var j: integer;
repeat
a[1:n+1].Println; //вывод очередной перестановки 12..n
var i := n;
while (a[i — 1] > a[i]) do i -= 1;
j := i — 1; // индекс1 = стоящий слева от MAX двигаясь справа налево
while (a[i + 1] > a[j]) do i += 1; {индекс2 = 'элемент справа от индекс1
со значением большим значения индекс1}
( a[j], a[i] ) := ( a[i], a[j] ); //поменять местаами
{цикл зеркально переворачивает в текущей перестановке
значения справа от индекс1, и т.о. сортирует по возрастанию}
var o := j + 1;
var k := n;
While (o < k) do
begin
( a[o], a[k] ) := ( a[k], a[o] );
o += 1;
k -= 1;
end;
until j = 0;
end.
Реализация на Fotran в виде подпрограммы
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
integer :: i,j,o,k,n,e,t,iperm,a(0:n+1)
integer,allocatable,save:: perm(:,:)
integer,save:: nperm
a = 0; iperm = 0
nperm = product([(i,i=1,n)])
allocate(perm(nperm,n))
do e = 1, n; a(e) = e; enddo
do
iperm = iperm + 1
write(*,*) a(1:n)
perm(iperm,:) = a(1:n)
i = n
do while (a(i — 1) > a(i))
i = i — 1
enddo
j = i — 1
do while (a(i + 1) > a(j))
i = i + 1
enddo
t = a(i); a(i) = a(j); a(j) = t
o = j + 1
k = n
do while (o < k)
t = a(o); a(o) = a(k); a(k) = t
o = o + 1
k = k — 1
enddo
if (j == 0) exit
enddo
endsubroutine Permutation
Большое спасибо за описанную реализацию перестановок с повторениями!
Благодаря Вам получилось быстро решить задачу
https://www.codewars.com/kata/5254ca2719453dcc0b00027d
А как быть в том случае, если количество элементов в исходном множестве элементов меньше, чем в искомом комбинаторном наборе? Например, нужно получить все перестановки с повторениями из множества четырех элементов по 10 элементов (в каждой перестановке)?
генерация размещений с повторениями
[Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).]
Здравствуйте! Скажите пожалуйста, никак не могу понять. Если идти справа налево в отсортированной последовательности, то мы не встретим элемента больше предыдущего. Можете пожалуйста добавить примеров или просто объяснить. Что-то никак не разберусь)
Как это не встретим? Если у нас текущая перестановка 1 3 2. Идём справа налево, 3>2. Встретили. А в отсортированный последовательности первым делом меняются два последних элемента.
Елена, спасибо большое за представленный алгоритм. Данный способ был использован для нахождения минимальной суммы произведений соседних элементов произвольного массива:
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
#include <stdbool.h>
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
/*—————————————————*/
bool seting (int *a, int n)
{
int b = true;
int j = n — 2;
while (j != -1 && a[j] >= a[j + 1])
{
j—;
}
if (j == -1)
{
b = false; // больше перестановок нет
}
int k = n — 1;
while (a[j] >= a[k])
{
k—;
}
swap(a, j, k);
int l = j + 1;
int r = n — 1; // сортируем оставшуюся часть последовательности
while (l<r)
{
swap(a, l++, r—);
}
return b;
}
/*—————————————————*/
int out(int *a, int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += a[i] * a[i + 1];
}
return sum;
}
/*————————————————*/
void outArr(int *a, int n)
{
for (int i = 0; i < n; i++) printf("%d ",a[i]);
}
/*———————————————-*/
int main()
{
int n = 5;
int c[n];
int a[] = { 1, 2, 3, 4, 5 };
printf ("Input array: ");
outArr (a, n);
for (int i = 0; i < n — 1; i++)
{
if (a[i] > a[i + 1]);
swap (a, i, (i + 1));
}
int min = out(a, n);
while (seting(a, n))
{
if (min > out(a, n))
{
min = out(a, n);
for (int j = 0; j < n; j++)
c[j] = a[j];
}
}
printf ("\n\n\nMin sum = ");
printf ("%d\nNew array: ", min);
outArr(c, n);
return 0;
}
Спасибо!
Здравствуйте, а если мне нужно найти все варианты перестановок комбинации чисел 33898, по формуле получается 5!/(2!*2!*1!) = 30, по способу описанному в программе получается всего 27 вариантов, как это можно исправить? Или где об этом можно узнать?
Если известно количество чисел, то быстрее и лучше решать задачу с использованием вложенных циклов.
В Вашем примере числа стоят не в лексикографическом порядке (не по возрастанию), поэтому и теряются начальные комбинации.
Отсортируйте числа по возрастанию прежде, чем генерировать перестановки.
Очень прошу помочь с решение.
Как определить максимальное количество комбинаций от
1 2 3 4 5, без единого повторения.
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 4 3 2 1
а далее голова может придумать еще 1-2, хотелось бы понять какой максимум.
5 3 4 1 2 — это повторение. уже ошибка.
Спасибо
и второй вариант количество с 1 пересечением.
очень благодарен если отправите решение.
Количество перестановок из 5 чисел без повторений будет 5!=120:
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
И т.д.
Если одно число повторяется, то количество перестановок будет в 2 разр меньше, т.е 60.
Все коды реализации есть в тексте статьи.
ЕЛЕНА, ЗДРАВСТВУЙТЕ! ПОМОГИТЕ ПОЖАЛУЙСТА СОСТАВИТЬ ВСЕ КОМБИНАЦИИ ОТ 0 ДО 9 ЧИСЕЛ ДЛЯ 6-ЗНАЧНОГО ПАРОЛЯ
Сделайте 6 вложенных циклов, каждый от 0 до 9.
Имеется перестановка с особенностью, например n(6)=123456. Особенность в том, что члены, стоящие на нечетных позициях меньше членов стоящих на четных. Подскажите, как модифицировать приведенный Вами алгоритм, чтобы все получаемые последующие перестановки сохраняли это же свойство. Общее число таких перестановок существенно меньше N=6!/(3!*2!*2!*2!)=15 (Производные перестановки, например от 123456: 125634,563412,345612 и т.д. считаются неразличимыми и могут не вычисляться). Метод «грубой силы» когда каждая перестановка проверяется на соблюдение этого условия не подходит, т.к. в реале уже при n(>10) работает очень медленно. Мне не нужна программа. Достаточно идеи.Или может дадите ссылки?
Ну, допустим таких перестановок будет не 15, а 90 🙂
И если известно число n, то более эффективно использовать вложенные циклы, а не рекурсию:
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
using namespace std;
int main()
{
int count = 1;
for (int n1 = 1; n1 <= 6; n1++)
{
for (int n2 = 1; n2 <= 6; n2++)
{
if (n2 == n1) continue;
for (int n3 = 1; n3 <= 6; n3++)
{
if (n3 == n1) continue;
if (n3 == n2) continue;
for (int n4 = 1; n4 <= 6; n4++)
{
if (n4 == n1) continue;
if (n4 == n2) continue;
if (n4 == n3) continue;
for (int n5 = 1; n5 <= 6; n5++)
{
if (n5 == n1) continue;
if (n5 == n2) continue;
if (n5 == n3) continue;
if (n5 == n4) continue;
for (int n6 = 1; n6 <= 6; n6++)
{
if (n6 == n1) continue;
if (n6 == n2) continue;
if (n6 == n3) continue;
if (n6 == n4) continue;
if (n6 == n5) continue;
if (n1 > n2) continue;
if (n3 > n4) continue;
if (n5 > n6) continue;
cout << fixed;
cout.width(3);
cout << count++ << ": ";
cout << n1 << " " << n2 << " " << n3 << " ";
cout << n4 << " " << n5 << " " << n6 << endl;
}
}
}
}
}
}
getchar();
return 0;
}
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
#include <malloc.h>
void swapInts(int pos1, int pos2, int arr[]) {
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
void printArray(int length, int arr[]) {
for (int i=0; i < length; i++) {
printf("%d ", arr[i]);
}
putchar('\n');
}
void printPermutations(int index, int length, int arr[]) {
if (index == length) {
printArray(length, arr);
return;
}
for (int i=index; i < length; i++) {
swapInts(i, index, arr);
printPermutations(index + 1, length, arr);
swapInts(i, index, arr);
}
}
int main(int argc, char *argv[]) {
int length;
printf("Type length of array: ");
scanf("%d", &length);
int *arr = malloc(length*sizeof(int));
printf("Type elements of array: ");
for (int i=0; i < length; i++) {
scanf("%d", &arr[i]);
}
printPermutations(0, length, arr);
return 0;
}
Добрый днь. подскажите как сделать перестановку слов от 1 до 5?
к примеру 1цифра это одно слово. имеется 4 слова.
нужно:
1
2
3
4
11
12
21
31
32
43
14
41
111
124
431
444
431
и т.д.
А где например 22, 13, 33, 44?
Из каких соображений эти перестановки опущены?
И почему 431 два раза?
привел просто пример. так они идут по порядку. (слишком много вариантов).
т.е. начинаются с 1 слово и заканчивается 5. (к примеру имеется 4 слова (dog cat duck banana) и их нужно перемешать со все возможными вариантами от 1 до 5)
Посмотрите алгоритм <a href="/placement/" rel="nofollow">генерации размещений с повторениями</a>.
Нужно вызвать этот алгоритм для M=1, 2, 3, 4.
Ну, а чтоб связать со словами, каждому значению поставить в соответствие слово: строка 22 изменится на
2
3
4
5
6
7
{
case 1: cout << word1 << " "; break;
case 2: cout << word2 << " "; break;
case 3: cout << word3 << " "; break;
case 4: cout << word4 << " "; break;
}
Там же в репозитариях аккаунта размещения, сочетания, разбиения, композиции. Все прокомментировано на русском и английском.
Всего 8 переборных алгоритмов классической комбинаторики:
https://github.com/dcc0
Надеюсь, кому-нибудь пригодится.
https://github.com/dcc0/permutations/tree/master/.gitignore
Перестановки с повторением и без. Итеративно. Без рекурсии.
Просто и красиво. Главное — короткая программа.
Жаль немного, что это не на Паскале, но ничего.
Спасибо.
Спасибо Вам Огромное, Елена, за тот невероятный потенциал который Вы привносите. Спасибо огромное за Вашу отзывчивость и оказанную помощь. С Уважением, адъюнкт Военной Академии г. Санкт-Петербург (капитан Романов Р.С.)
Здравствуйте Вы не могли бы мне помочь с этой программой не могу понять что и как ! Мне нужно определить последовательности для 5 чисел (1,2,3,4,5)! Спасибо . напишите на почту !
Алгоритм перестановки с повторениями немного неправильно работает, ибо P(4)=12600, а не 12.
Не поняла, откуда Вы взяли такое гигантское число?
P=(1+2+3+4)!/(1!2!3!4!)
Нет, P=4!/(2!·1!·1!) (для выбранного набора значений — 1,1,3,4. То есть P = 24/2 = 12.
В вашем первом посте приведен алгоритм получения одной перестановки из другой. В алгоритме получения всех перестановок множества это только часть задачи.
Этот алгоритм предназначен для получения следующей перестановки в лексикографическом порядке. Для генерации всех перестановок функция <span class="prog">NextSet()</span> должна вызываться в цикле. Условием выхода из цикла является значение <span class="prog kwd">false</span>, которое возвращает функция <span class="prog">NextSet()</span>, что означает, что больше перестановок не найдено.
Нужны варианты перестановки n=6 без повторений. Среди них выбрать регулярные
Смотрите код в комментарии выше