Перестановки чисел

[Marleny]

Помогите запрограммировать такую штуку: вводится число классов, в каждом классе число элементов (например числа). Нужно получить строки заданной длины N из всевозможных перестановок этих чисел. Например, 4 класса, в них 2, 2, 1, 1 элементов: [1,1], [2,2], [3], [4], длина строки =3. Должно получиться:
112
113
114
121
122
123
124
131
132
134
141
142
143
211
212
213
214
221
223
232
234
241
242
243
311
312
314
321
322
324
341
342
411
412
413
421
422
423
431
432
Вся проблема в том, что заранее неизвестна длина строки N, и поэтому нельзя сделать просто определенное число вложенных циклов. Помогите пожалуйста!! очень нужно

[0xFFFFFF]

рекурсия?

[Marleny]

Белая
желательно нет

еще можно так сформулировать: есть массив элементов, например [1,1,2,2,3,4], нужно сделать все сочетания какой-то длины, например 3

[0xFFFFFF]

Белая
желательно нет

еще можно так сформулировать: есть массив элементов, например [1,1,2,2,3,4], нужно сделать все сочетания какой-то длины, например 3
ты мне поработать предлагаешь? сам-то как пробовал?
и чем тебе не нравится рекурсия?

[etc]

Marleny,
2.718281828459045 (exp) [Сделайте всё за меня] (http://www.flasher.ru/forum/showthread.php?postid=385935&t=6232#post385935)

[Marleny]

Я по-моему вполне понятно написала, что я делала (вложенные циклы), в чем проблема (неизвестно их количество). Я прошу предложить какой-то алгоритм, или подсказать идею реализации. Если кто-то считает, что я просто прошу все сделать за меня и ничего не пытаюсь сделать сама, то это не так. Хотя, конечно, каждый имеет право на собственное мнение. Единственная просьба - если не хотите или не можете предложить что-то конкретно по задаче, не стоит тыкать меня в тему "делай все за меня" или наподобие.

Белая
Я тебе поработать не предлагаю, а прошу помочь.

[0xFFFFFF]

я же говорю РЕКУРСИЯ.
у меня всё получилось.
других выходов пока не вижу.

[iNils]

Можно и без рекурсии, но алгоритм сложнее.

[0xFFFFFF]

Можно и без рекурсии, но алгоритм сложнее.
как например?

[iNils]

как например?
Конечно через циклы.

[0xFFFFFF]

Конечно через циклы.
и как ты предлагаешь неограниченное кол-во вложенных циклов сделать?

[tonnon]

я как-то вывел формулу:) может пригодится
если даны три числа то комбинаций может быть 6:
123
132
213
231
312
321
получается: кол-во комб = 3*2. если 4 числа то 4*3*2, если 5 то 5*4*3*2 ну и т.д. я все проверил!

[iNils]

и как ты предлагаешь неограниченное кол-во вложенных циклов сделать?
А не нужно неограниченное количество делать. Здесь как в часах, смена секундной стрелки с 59 на 0, дает смещение минутной на 1. Ну и так далее.

[0xFFFFFF]

я как-то вывел формулу:) может пригодится
если даны три числа то комбинаций может быть 6:
123
132
213
231
312
321
получается: кол-во комб = 3*2. если 4 числа то 4*3*2, если 5 то 5*4*3*2 ну и т.д. я все проверил!
хахахахааа!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
мы это в школе проходили :)))

[0xFFFFFF]

А не нужно неограниченное количество делать. Здесь как в часах, смена секундной стрелки с 59 на 0, дает смещение минутной на 1. Ну и так далее.
хм... имхо с рекурсией проще будет

[iNils]

я как-то вывел формулу:) может пригодится
если даны три числа то комбинаций может быть 6:
123
132
213
231
312
321
получается: кол-во комб = 3*2. если 4 числа то 4*3*2, если 5 то 5*4*3*2 ну и т.д. я все проверил!
Не совсем верно. Могут использоваться цифры 1, 1, 2, 2, 3, 4. То есть единица в разных положениях может использоваться дважды, но! есть 1(первая) и есть 1(вторая) и использовать в комбинации 231 единицу можно только один раз, либо с первой либо со второй. Поэтому число комбинаций будет меньше.

[iNils]

хм... имхо с рекурсией проще будет
См пост 8

[0xFFFFFF]

Не совсем верно. Могут использоваться цифры 1, 1, 2, 2, 3, 4. То есть единица в разных положениях может использоваться дважды, но! есть 1(первая) и есть 1(вторая) и использовать в комбинации 231 единицу можно только один раз, либо с первой либо со второй. Поэтому число комбинаций будет меньше.
комбинаторика как помню.. первый или второй курс?

[iNils]

комбинаторика как помню.. первый или второй курс?
Не помню, я еще в школе ей интересовался.

[Marleny]

iNils
то есть ты предлагаешь делать след. образом (arr=[1,1,2,2,3,4]), используя индексы:
012, увеличиваем 2 пока не станет равной 5,т.е:
012, 013, 014, 015
потом 5-->0, предыдущая цифра (1) увеличивается на единицу
020, 021, 022, 023и т.д.
а как в таком случае отлавливать ситуации, когда индексы повторяются? (020, 022,...)

[tonnon]

Не совсем верно. Могут использоваться цифры 1, 1, 2, 2, 3, 4. То есть единица в разных положениях может использоваться дважды, но! есть 1(первая) и есть 1(вторая) и использовать в комбинации 231 единицу можно только один раз, либо с первой либо со второй. Поэтому число комбинаций будет меньше.
эт я просто привел пример. я не говорил что эта формула будет решением

[0xFFFFFF]

эт я просто привел пример. я не говорил что эта формула будет решением
зачем? выпендриться?

[Nirth]

зачем? выпендриться?
Какая ты злая стала

[0xFFFFFF]

Какая ты злая стала
я?? злая? не люблю пустой выпендреж :))

[Nirth]

человек высказал идею...

[iNils]

iNils
то есть ты предлагаешь делать след. образом (arr=[1,1,2,2,3,4]), используя индексы:
012, увеличиваем 2 пока не станет равной 5,т.е:
012, 013, 014, 015
потом 5-->0, предыдущая цифра (1) увеличивается на единицу
020, 021, 022, 023и т.д.
а как в таком случае отлавливать ситуации, когда индексы повторяются? (020, 022,...)
именно. а индексы проверять до первого свободного вверх.

[0xFFFFFF]

человек высказал идею...
извините, не заметила идеи...

[iNils]

извините, не заметила идеи...
Идея в том как заменить рекурсию, а заменить ее можно только зная максимальное (без исключений) число значений.

[Marleny]

Я нашла решение своей задачи. С помощью рекурсии. Всем спасибо, кто помог, вопрос решен, если кому-то интересно, вот алгоритм решения:
Начальный массив элементов: arr1=[1,1,2,2,3,4]
Длина строки: <=N
Формируем массив - элемент которого есть число одинаковых цифр в arr1: arrIndex1=[2,2,1,1]
st1 - строка, в которую накапливаем цифры.
При вызове функции необходимо указывать длину на 1 больше, чем нужно на самом деле

функция Цикл (N, st1, arrIndex1);
var st2:string;
arrIndex2: тип такой же, как arrIndex1;
{ st2=st1;
arrIndex2=arrIndex1;
if (N>1) {
{for (i=1; i<=arrIndex1.length(); i++)
{if (arrIndex1[i]>0)
{arrIndex1[i]--;
st1=st1+i;
вывод st1;
Цикл(N-1, st1, arrIndex1);
st1=st2;
arrIndex1=arrIndex2
}
}
}
}
}

[0xFFFFFF]

функция Цикл (N, st1, arrIndex1);
var st2:string;
arrIndex2: тип такой же, как arrIndex1;
{ st2=st1;
arrIndex2=arrIndex1;
if (N>1) {
{for (i=1; i<=arrIndex1.length(); i++)
{if (arrIndex1[i]>0)
{arrIndex1[i]--;
st1=st1+i;
вывод st1;
Цикл(N-1, st1, arrIndex1);
st1=st2;
arrIndex1=arrIndex2
}
}
}
}
}
это на каком языке? :eek:
за русский в коде убила бы..

[K.A.T.A.F.A.L.K.E.R]

за русский в коде убила бы..
Какая ты злая стала
..... :mosking:

[Marleny]

Белая
... вот алгоритм решения...
Это не код.
Вам, девушка, чрезмерная агрессия по жизни не мешает? Мало того, что единственным словом по теме было упоминание о рекурсии, так и после того, как тему можно закрыть, все равно какие-то реплики проскакивают не совсем понятные. Не нравится, не ешь, как говорится.

[Marleny]

Прошу модераторов закрыть тему

[K.A.T.A.F.A.L.K.E.R]

единственным словом по теме было упоминание о рекурсии
как по мне - это было единственное здравое слово на всю тему...