Рекурсивный алгоритм, печатающий все перестановки

echs · Регистрация: 23.10.2013

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

Дано десять цифр 0, 1, 2, ... 9
(Но для отладки я использую 3-4 цифры. Это удобно)
Требуется распечатать все перестановки этих чисел, используя
рекурсивный алгоритм.
1. Собственно эта задача легко решается и без рекурсии, если
использовать 10-кратный цикл.
2. Но нужен именно рекурсивный алгоритм.
Я мыслю это так:
1) задается массив, заполненный цифрами 0, 1, ... 9
2) вызывается рекурсивная процедура с параметром n=10
3) в процедуре цикл, который в первый элемент массива
вставляет по очереди числа 0, 1, ... 9 и вызывает рекурсивную
процедуру с параметром на 1 меньше (она вызывается 10 раз)
Вопросы
1. Как остановить процедуру?
2. Она печатает с повторениями. Как этого избежать?
3. Строки разной длины?
4. Короче, я не знаю. И делаю не то. Кто подскажет?

@SlavaSSU · 23.11.2015, 23:13

geh, можно не думать и написать перебор.

C++ (Qt)

int n;
int a[10];
bool used[10];
 
void brute(int m) {
    if (m == n) {
        for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << endl;
        return;
    }
 
    for (int nxt = 0; nxt < n; nxt++) {
        if (!used[nxt]) {
            used[nxt] = true;
            a[m] = nxt;
            brute(m + 1);
            used[nxt] = false;
        }
    }
 
    return;
}
 
inline void solve() {
    cin >> n;
    brute(0);
    return;
}

@Shamil1 · 24.11.2015, 02:34

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

C#

void Main()
{
    "0123".Aggregate(
        new string[] {""}.AsEnumerable(),                       //seed
        (perms, ch) => perms.SelectMany(x => InsertChar(x, ch)) //func
                    ).Dump();
}
 
// вставляем символ в строку на все позиции
IEnumerable<string> InsertChar(string str, char ch)
{
    for(int i = 0; i <= str.Length; i++)
        yield return str.Insert(i, ch.ToString());
}

@S_el · 24.11.2015, 03:10

geh, обсуждалось неоднократно:
Перестановка чисел в числе
Какой алгоритм? Не смог реализовать на Python

echs · 24.11.2015, 11:20 **[ТС]**

Ребята. Спасибо! Я вам крайне благодарен.
Я получил не только алгоритм но и кучу идей,
которые мне пригодятся в ближайшем будущем.
Спасибо! Спасибо! Спасибо!

echs · 29.11.2015, 11:45 **[ТС]**

Этот алгоритм и был моей целью.

QBasic/QuickBASIC

REM  
REM  Программа печатает все перестановки
REM                из N элементов 
REM
 
DECLARE SUB P (k%)
 
CLS
CLEAR , , 20000
 
DIM SHARED n AS INTEGER
n = 4
DIM SHARED x(1 TO n) AS INTEGER
 
FOR i = 1 TO n
   x(i) = i
NEXT i
 
CALL P(0)
END
 
SUB P (k AS INTEGER)
 
   IF k = n THEN
      FOR j = 1 TO n
         PRINT x(j);
      NEXT j: PRINT
   ELSE
      FOR i = k + 1 TO n
         SWAP x(k + 1), x(i)
         CALL P(k + 1)
         SWAP x(k + 1), x(i)
      NEXT i
   END IF
END SUB

Рекурсивный алгоритм, печатающий все перестановки

Решение

Решение

Решение

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
		1
	Рекурсивный алгоритм, печатающий все перестановки 23.11.2015, 21:14. Показов 1838. Ответов 5 Метки нет (Все метки) Дано десять цифр 0, 1, 2, ... 9 (Но для отладки я использую 3-4 цифры. Это удобно) Требуется распечатать все перестановки этих чисел, используя рекурсивный алгоритм. 1. Собственно эта задача легко решается и без рекурсии, если использовать 10-кратный цикл. 2. Но нужен именно рекурсивный алгоритм. Я мыслю это так: 1) задается массив, заполненный цифрами 0, 1, ... 9 2) вызывается рекурсивная процедура с параметром n=10 3) в процедуре цикл, который в первый элемент массива вставляет по очереди числа 0, 1, ... 9 и вызывает рекурсивную процедуру с параметром на 1 меньше (она вызывается 10 раз) Вопросы 1. Как остановить процедуру? 2. Она печатает с повторениями. Как этого избежать? 3. Строки разной длины? 4. Короче, я не знаю. И делаю не то. Кто подскажет? 0

@S_el 2443 / 1841 / 406 Регистрация: 15.12.2013 Сообщений: 8,238
	24.11.2015, 03:10	4
	Сообщение было отмечено echs как решение Решение geh, обсуждалось неоднократно: Перестановка чисел в числе Какой алгоритм? Не смог реализовать на Python 1

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	24.11.2015, 11:20 [ТС]	5
	Ребята. Спасибо! Я вам крайне благодарен. Я получил не только алгоритм но и кучу идей, которые мне пригодятся в ближайшем будущем. Спасибо! Спасибо! Спасибо! 0

	29.11.2015, 11:45