Получение всех перестановок заданных объектов , не понимаю как это надо делать (может через рекурсию)

Всем привет!

Есть такая задачка: Дано N объектов (N = [1 .. 6]), которые могут принимать M значений (M = [1 .. 5]).
Получить все возможные перестановки/размещения с повторениями данных объектов.

Для примера, если N = 4, M = 3, то код может быть таким (если заранее жестко известны значения N, M):

#include "stdafx.h"
#include <iostream>
 
using namespace std;
const int M = 3;
int main()
{
    long long n = 0;
    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= M; j++)
            for(int k = 1; k <= M; k++)
                for(int l = 1; l <= M; l++)
                    cout << ++n << ":\t" << i << j << k << l << endl;
    cin.get();
    return 0;
}

Получается 81 цепочка, что соответствует формуле из комбинаторики размещения с повторениями = M^N = 3^4 = 81 набор.
Но это тупой, топорный, абсолютно негибкий вариант, т к N, M будут задаваться динамически во время выполнения программы.

В этом алгоритме полного перебора к чему стремиться? К построению дерева, к рекурсии или еще как-то?
P.S. находил описания в сети чего-то похожего + даже код был на Паскале, но глубоко не могу понять этот алгоритм...

Рекурсия?

Цитата Akina @ 24.11.16, 15:31

Рекурсия?

ну, допустим, да!
но я не понимаю, как через нее сделать

P.S. максимально вызовов будет 5^6 = 25^3 = 15 625 рекурсивной функции. Это ведь вроде немного...

Цитата FasterHarder @ 24.11.16, 15:36

я не понимаю, как через нее сделать

Передаёшь в функцию текущий недовариант и уровень. Если уровни вычерпаны - выводишь, иначе дописываешь по одному элементу и шлёшь на следующий виток.

Как вариант вместо рекурсии - непосредственная генерация следующего элемента. Как-то так:

const int N = 6, M = 5;
int a[N];
for(int i = 0; i < N; ++i) a[i] = 1;
do
{
    for(int i = 0; i < N; ++i) std::cout << a[i] << " ";
    int i = 0;
    while(i < N && a[i] == M)
    {
        a[i] = 1;
        ++i;
    }
    if(i == N) break;
    ++a[i];
} while(true);

Добавлено 24.11.16, 15:58
И то, что тебе надо, называется не перестановками, а размещениями с повторением.

Народ, какая рекурсия? Это же просто получение записи всех чисел от 0 до M^N-1 в M-ричной системе счисления с заменой символов "0" на "1", "1" на "2" и т. д.
Вот на бейсике:

Sub Main()
  Dim N As Long, M As Long
  Dim i As Long, ii As Long, j As Long, Cnt As Long
  Dim Res As String
 
  N = 4
  M = 3
  Cnt = M ^ N
 
  For i = 1 To Cnt
    ii = i
    Res = ""
    For j = 0 To M
      Res = Res & Chr(49 + (ii Mod M))
      ii = ii \ M
    Next j
    Debug.Print Res
  Next i
End Sub

А, допустим, не знали бы мы, что получится их 3⁴; как бы ваш код, Mikle, изменился?..

Он бы просто новые значения N и M подставил. Другое дело, что конкретно эта программа (на бейсике или транслированная на подавляющее большинство ЯП) не любую комбинацию N, M потянет.
В отличие от программы OpenGL, которая получилась такой же короткой и быстрой (будучи реализованными на одном языке эта программа скорее всего окажется даже быстрее), и где тоже достаточно поменять значения N, M.

Цитата amk @ 26.11.16, 11:19

Он бы просто новые значения N и M подставил.

Я не понял ваш ответ, amk. Если бы мы не знали, что итог - это возведение числа в степень другого числа, то как бы изменилась прога Mikle?

Так, давайте еще внесем НЕБОЛЬШУЮ ясность! Забыл написать об этом изначально)
Вывод должен быть в лексикографическом порядке, поэтому код из поста №5 нужно допиливать! Да, может быть чуть-чуть, но нужно!

P.S. Для натуральных чисел лексикографический порядок выводит по возрастанию
1111
1112
1113
1121
....
3333

Добавлено 26.11.16, 12:53
И это, давайте поменьше кода и побольше алгоритмизации, т к поняв алгоритм, я как бы сам должен суметь закодить! Ну, это в идеале. А на практике уйдет не один месяц, чтобы понять глубоко данный алгоритм.

Добавлено 26.11.16, 13:05
Предпочтение отдается рекурсии!
Akina поверхностно объяснил (дал идею), буду думать...

Цитата FasterHarder @ 26.11.16, 12:51

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

В п.6 именно так. И идея там изложена, не только код:

Цитата

Это же просто получение записи всех чисел от 0 до M^N-1 в M-ричной системе счисления с заменой символов "0" на "1", "1" на "2" и т. д.

Цитата Славян @ 26.11.16, 10:05

А, допустим, не знали бы мы, что получится их 34; как бы ваш код, Mikle, изменился?

Если бы я этого не знал, через минуту я бы уже до этого сам догадался.

Сообщение отредактировано: Mikle - 26.11.16, 13:09

Цитата Славян @ 26.11.16, 12:08

Если бы мы не знали, что итог - это возведение числа в степень другого числа

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

Цитата FasterHarder @ 26.11.16, 12:51

Вывод должен быть в лексикографическом порядке, поэтому код из поста №5 нужно допиливать! Да, может быть чуть-чуть, но нужно!

Просто иди во внутреннем while не от 0 до N, а наоборот. Ну или просто выводи их в перевёрнутом виде.

Сообщение отредактировано: OpenGL - 26.11.16, 18:10

Народ резко бросился прогать!

Цитата FasterHarder @ 26.11.16, 12:51

Так, давайте еще внесем НЕБОЛЬШУЮ ясность!

А давайте!

Так всеж или перестановки нужны? Или размещения? Туманишь ты народ непадецки
Термины разные, расчеты разные ... определись, что именно нужно!

В условии написано, что размещения с повторениями!

Вот заготовка программы на С++(там нет главного):

#include "stdafx.h"
#include <iostream>
using namespace std;
//----------------------------------------------------
// Вывод последовательности цифр на экран
//----------------------------------------------------
void PrintSequence(const int* const pv, const int pcount, const int pID)
{
    cout << pID << ":\t";
    for(register int i = 0; i < pcount; i++)
        cout << pv[i];
}
//----------------------------------------------------
int main()
{
    setlocale(LC_ALL, "");
    cout << "Введите количество объектов/цифр для обработки из отрезка [2 .. 6]: ";
    int count;
    cin >> count;
    cout << "Введите максимальное значение, принимаемое цифрой, из отрезка от [2 .. 9]: ";
    int maxValue;
    cin >> maxValue;
    int *v = new int[count];
    // инициализация всех цифр значением 1
    for(int i = 0; i < count; i++)
        v[i] = 1;
    int ID = 0;
    PrintSequence(v, count, ++ID);
    cin.get();
    cin.get();
    delete []v;     // динамический массив нужно уничтожить при выходе из программы!
    return 0;
}

Т е в программу подается количество цифр в последовательности + диапазон значений(левая граница = 1 - присваивается при инициализации).
Т к нужна рекурсия, то я хочу понять, что является элементарным случаем рекурсии. Например, когда рассчитывается факториал числа, то элементарным случаем является такое условие:

if(pn < 2)
    return 1;

если делается обход бинарного дерева поиска, то элементарный случай возникает тогда, когда текущий узел является ЛИСТОМ.

А, что в данном случае является элементарным случаем рекурсии? Когда все цифры стали равны maxValue?

Сообщение отредактировано: FasterHarder - 29.11.16, 17:54