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

Всем привет!

Есть такая задачка: Дано 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

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

Если это счётчик в массиве, то вызов с отрицательным индексом (дошли до первого элемента (индекс 0), увеличили его до предела, попытались вызвать функцию для более левого элемента)

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

Поэтому хочу сразу понять, можно ли написать ОДНУ рекурсивную функцию, которая будет размещать как надо или это невозможно?

>ожно ли написать ОДНУ рекурсивную функцию

А зачем больше рекурсивных функций ???

Цитата MBo @ 29.11.16, 18:25

А зачем больше рекурсивных функций ???

так я и интересуюсь, т к не знаю просто в том коде была какая-то вспомогательная функция!

Цитата MBo @ 29.11.16, 18:08

Если это счётчик в массиве, то вызов с отрицательным индексом (дошли до первого элемента (индекс 0), увеличили его до предела, попытались вызвать функцию для более левого элемента)

так, понял вроде

нужно попытаться составить заголовок рекурсивной функции (все параметры прокомментированы):

//----------------------------------------------------
// Получение размещений с повторениями
// pv - последовательность размещаемых объектов/цифр
// pi - индекс переставляемого объекта/цифры (отсчет по правилам массивов С++)
// pmaxValue - максимальное значение, принимаемое объектом/цифрой
// pID - номер текущей последовательности (нужно для вывода на экран)
//----------------------------------------------------
void Deployment(int *pv, int pi, int pmaxValue, int pID)
{
}
//----------------------------------------------------

из функции main() первый раз вызывается так:

Deployment(v, count - 1, maxValue, ID);

тут все норм. или что-то не учтено, что пригодится?

В итоге чертовщина какая-то получилась, т к до конца еще не разобрался с этим алгоритмом:

//----------------------------------------------------
// Получение размещений с повторениями
// pv - последовательность размещаемых объектов/цифр
// pi - индекс переставляемого объекта/цифры (отсчет по правилам массивов С++)
// pmaxValue - максимальное значение, принимаемое объектом/цифрой
// pID - номер текущей последовательности (нужно для вывода на экран)
// pcount - количество объектов/цифр в последовательности
//----------------------------------------------------
void Deployment(int *pv, int pi, int pmaxValue, int pID, int pcount)
{
    if(pi >= 0) // когда pi = -1, то процедура закончена!
    {
        PrintSequence(pv, pcount, pID);
        if(pv[pi] < pmaxValue)
        {
            pv[pi]++;
            Deployment(pv, pi, pmaxValue, ++pID, pcount);
        }
        else
        {
            pv[pi - 1]++;
            pv[pi] = 1;
            Deployment(pv, pi - 1, pmaxValue, ++pID, pcount);
        }
    }
}
//----------------------------------------------------

Есть следующие вопросы:

1. Если рекурсия на спуске, то получаем в возрастающем лексикографическом порядке, а, если на возврате, то в убывающем, да?
2. В теле рекурсивной функции не должно быть никаких циклов? Вообще рек.функция должна выполнять действия: либо увеличение на 1 нужной цифры,
либо переход на следующий разряд, стоящий слева от текущего и увеличение его на 1, и выставление какого-то разряда в 1?
3. Есть что-то общее в этой рек.функции с рек.функциями, которые используют в сильноветвящихся деревьях?

Допустим, дано 4 объекта, которые принимают значения {1, 2}
1: 1111
2: 1112
3: 1121
4: 1122
5: 1211
...
Вот мне абсолютно непонятно по цепочке 1211, на каких копиях рекурсивных функциях будут выставлены 1 и 1 в двух правых цифрах.

P.S. Бинарные деревья поиска и то были более понятными...

Если неприменно нужна рекурсия, вот:

Const N As Long = 3, M As Long = 2
Dim Ar(N - 1) As Long
 
Sub Main()
  Dim i As Long
 
  For i = 0 To N - 1
    Ar(i) = 1
  Next i
  NextVal
End Sub
 
Sub NextVal()
  Dim i As Long
 
  PrintAr
  i = N - 1
  While i >= 0
    Ar(i) = Ar(i) + 1
    If Ar(i) > M Then
      Ar(i) = 1
      i = i - 1
    Else
      NextVal
      Exit Sub
    End If
  Wend
End Sub
 
Sub PrintAr()
  Dim i As Long
 
  For i = 0 To N - 1
    Debug.Print Ar(i);
  Next i
  Debug.Print
End Sub

sub recurse(currentvariant, currentlevel)
if currentlevel = 0 then
    print currentvariant
else
    for i = 1 to statescount
        call recurse(currentvariant & states(i), currentlevel - 1)
    next i
end if
end sub ' recurse
 
public const statescount = someinteger
public states(1 to statescount) as sometype
 
sub Main
for i = 1 to statescount
    states(i) = somevalue
next i
call recurse(empty, levelsneeded)
end sub ' Main

for i in 1 to C
GENERATE_Random_Pemutation


вот весь код
С = максимальное количество пермутаций * логарифм от максимального количества пермутаций умножить на 10

Алгоритм вероятностный