0 / 0 / 0
Регистрация: 25.09.2017
Сообщений: 15
1

Сгенерировать всевозможные перестановки N чисел без повторений

21.04.2018, 01:14. Показов 7162. Ответов 22
Метки с (Все метки)

Author24 — интернет-сервис помощи студентам
Условие задачи: Сгенерировать всевозможные перестановки N чисел без повторений. (Использовать рекурсию, функции и массивы нельзя, выполнять через циклы for)
Эта задачка вынесла мою нервную систему.
Вводим 123
На выводе нужно: 123 132 213 231 312 321
Насколько я понимаю это делается остатком от деления, но хвосты в универе не позволяют поломать голову над задачкой поплотнее. Надеюсь на вашу помощь, товарищи.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.04.2018, 01:14
Ответы с готовыми решениями:

Перестановки без повторений
Как из этого кода сделать конфетку — чтобы не выводились повторения? #include <iostream> ...

Перестановки без повторений
Требуется дописать исключение повторений в коде,спасибо. #include <iostream> using namespace...

Перестановки без повторений
привет помогите пожалуйста найти файлик в котором бы были все перестановки из 5 элементов. ...

Даны n чисел в произвольном порядке, вывести на экран всевозможные их перестановки
Даны n чисел в произвольном порядке. Вывести на экран всевозможные их перестановки. Есть у...

22
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
22.04.2018, 01:03 21
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от Байт Посмотреть сообщение
для произвольного 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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
 
using namespace std;
 
int f(int n, int p, int k) {
    for(int i = 0; i < k-p-1; i++) {
        n/=10;
    }
    return n%10;
}
 
void swp(int& n, int k, int a, int b) {
    int p = 0;
    for(int i = 0; i < k; i++) {
        if (i == a) p = p*10+f(n, b, k);
        else if (i == b) p = p*10+f(n, a, k);
        else p = p*10+f(n, i, k);
    }
    n = p;
}
 
void reverse(int& n, int k, int a, int b) {
    int p = 0;
    for(int i = 0; i < a; i++) {
        p = p*10+f(n, i, k);
    }
    for(int i = k-1; i >= a; i--) {
        p = p*10+f(n, i, k);
    }
    n = p;
}
 
bool next_permutation(int& n, int k){
 
    for(int i = k-2; i>=0; i--) {
        int min = -1;
        if (f(n, i, k) < f(n, i+1, k)) {
            min = i+1;
            for(int j = i+1; j < k; j++) {
                if (f(n, j, k) <= f(n, min, k) && f(n, j, k) > f(n, i, k)) {
                    min = j;
                }
            }
            swp(n, k, i, min);
            reverse(n, k, i+1, k-1);
            return true;
        }
    }
    return false;
}
 
int main() {
    int n, k;
    cin >> n >> k;
    cout << "1 " << n << endl;
    int i = 2;
    while(next_permutation(n, k)) {
        cout << i++ << " " << n << endl;
    }
    return 0;
}
Функции осталось бахнуть куда нужно. swp, reverse переносятся без проблем. f(n, i, k) движется всегда в одну сторону. так что проблем не будет.
0
0 / 0 / 0
Регистрация: 25.09.2017
Сообщений: 15
22.04.2018, 12:32  [ТС] 22
это вообще далеко от того, что нужно
Там должно быть все куда проще, во-первых.
А во-вторых, (это код, выполняющий другую немного задачу, но в целом очень схож и структура требуемая) нужно убрать ввод с клавиатуры, переменную k загнать в счетчик вычисления разрядности for(k;k<N;k++){...}
Но тут я снова сталкиваюсь с проблемой - где-то в коде баги.
Именно вот такой код должен быть, но нужно разобрать что лишнее\нехватает
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
#include <iostream> 
using namespace std; 
int main() { 
    setlocale(LC_ALL, "rus"); 
    int N; 
    int k; 
    cout << "Введите число N:" << endl; 
    cin >> N; 
    cout << "Введите число k:" << endl; 
    cin >> k; 
    cout << "Все k-элементные подмножества:" << endl; 
    int t = k - 1; 
    int i; 
    int j; 
    int v = 1; 
    for (int l = 0; l <= N - k; ++l) 
    { 
        for (j = t + 1; j <= N; j++) 
        { 
            for (i = v; i <= t; i++) 
            { 
                cout << i; 
            } 
        cout << j << endl; 
        } 
    v++; 
    t++; 
    } 
system("pause"); 
return 0; 
}
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
22.04.2018, 13:38 23
Цитата Сообщение от KillerLongevity Посмотреть сообщение
это вообще далеко от того, что нужно
Еще раз.
Нужно вывести все перестановки. Они выведены? Да. Правильно? Да. В чем проблема?
Перестановки генерятся 3 способами. Рекурсия. Next_permutation и коды грея.
Рекурсия не катит.
Переставноку написал - вам не нравится
Грей - будет проблема с повторениями.
Можно еще придумать ересь. Давайте, например, выводить перестановку по номеру. Но это совсем маразм. Там нужно факториалы считать. И проходиться по числу.

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

Цитата Сообщение от KillerLongevity Посмотреть сообщение
это код, выполняющий другую немного задачу
Какую?
Вывести все подмножества из по k элементов из n? Дык не выполняет он ее
0
22.04.2018, 13:38
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.04.2018, 13:38
Помогаю со студенческими работами здесь

Сгенерировать случайные числа без повторений
Нужно выбрать 8 чисел в диапазоне от 1 до 16 включительно, чтоб они не повторялись. и записать в...

Выписать все перестановки без повторений
Тему копирую из раздела C#, из-за того что на си народу больше. Есть строка 0,1,2,3,4 и к...

Требуется написать перестановки без повторений
#include &lt;iostream&gt; using namespace std; const int N =11; int n,a,p; void f(int k){ if(k...

Сгенерировать массив размером 20 на 20 из чисел от 0 до 15. Сосчитать количество повторений каждого символа.
Всем здорово!Помогите пожалуйста с программами завтра рубежка...(на turbo C,не С++),если можно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru