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

[Litanika]

Помогите запрограммировать такую штуку: вводится число классов, в каждом классе число элементов (например числа). Нужно получить строки заданной длины 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, и поэтому нельзя сделать просто определенное число вложенных циклов. Помогите пожалуйста!! очень нужно

[Finch]

Litanika, Покажи на пальцах, как ты получил например первое число 112. Что то я никак не могу понять логику.

[Litanika]

Finch
Беру первый элемент из первого класса, затем если есть там еще элементы, беру еще элемент, если нет, то из следующего. Так последний элемент в строке (третий) перебираю по всем классам. Получилось 112, 113, 114
Затем откатываюсь на шаг назад, заменяю вторую единицу на 2: 12 и опять прохожу по всем классам, получаю: 121, 122, 123, 124. И т.д. Если в классе не хватает элемента (например 313 не получается, т.к. тройка одна), то эта комбинация пропускается (по идее первой должна была быть строка 111, но единиц только 2)

[Finch]

Т.е. это все можно свести в один обший массив [1,1,2,2,3,4]. Из членов данного массива нужно составить все возможные комбинации с заданной длиной комбинации. Я правильно понял?

[Litanika]

Finch
да, точно. можно свести наверно в один массив.
мне вообще-то нужны будут все комбинации заданной длины в каком-то диапазоне, то есть например, макс. длина 15, то все строки длины 1, 2, 3, ..., 15.
Кстати,

Litanika, Покажи на пальцах, как ты получил например первое число 112. Что то я никак не могу понять логику.

я женского пола

[MS]

Litanika, а на чем тебе это нужно написать?

[MS]

Немогу точно объястить,  примерно так:
берем первый элемент меняем местами со вторым, выводим, потом с третьим и т.д.
так с каждым, чтобы каждый элемент побывал на месте других, и после каждой комбинации вывод.
Вот

[Finch]

я женского пола

Извиняюсь если обидел. У тебя в профиле не указано. Значит исходим из обшего правила

В твоем случае всего всевозможных комбинаций 120 (6*5*4). Недавно поднималась тема с подобной задачей https://forum.shelek.ru/index.php/topic,8560.msg126526.html. Просмотри ее. Конечно нужно будет адаптировать под себя. Но в ней высказывалось несколько идей.

[Алексей++]

если представить всё в одном массиве, то искать нужно сочетание индексов.

 5  4  8   (<-массив)
 0  1  2   (<-индексы)

для случая массива длиной==3 и длины строки перестановок==3  алгоритм такой  (числа - это ИНДЕКСЫ):
("-" означает неверное сочетание, "--" означает переполнение одного из индексов. Правильное сочетание вынесено)
-------------------------------
      012
013--
020-
      021
022-
023--
030--
100-
101-
      102
103--
110-
      120
121-
122-
123--
130--
200-
      201
202-
203--
      210
211-
212-
213--
220-
230--
300-- стоп
-------------------------------


а реализацию чичас придумаю (если опять же не опоздаю)
мммм... или не усну ))))))

[Litanika]

MS, мне нужно написать на delphi. это часть большой задачи по мат. моделированию

[Алексей++]

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

[Litanika]

Алексей1153, можно хотя бы алгоритм, как там называется, на алгоритмическом языке, или как-то так, а то у меня от циферок уже голова болит...

[Алексей++]

Litanika, ну смотри в том посте:

содержание массива "классов" (как ты его называешь) нафик не важно. Важно - количество элементов.  Также имеется некий массив (назовём буфер для краткости), в котором перебираем сочетания. То есть исходные данные - длина массива "классов" (назовём его Arr) и длина буфера.
Элементы Arr - пронумерованы от 0 до (длина Arr -1)
В буфере - индексы массива Arr. То есть переставляем индексы только.

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

[Litanika]

Алексей1153,
эмм, ладно, спасибо, щас пойду пробовать, надеюсь получится

[Litanika]

вот например у меня в буфере 6 элементов: 0123456, длина комбинации - 4
я первое сочетание беру 0123 и перебираю до 6000? и я так понимаю, еще надо отлавливать, когда повторяются цифры, да? а вот как же это отловить?

[Алексей++]

Litanika,

Код:

struct XXX
{
	//nDestLen - это длина строки для перебора сочетаний
	//nSourLen - это количество элементов
	static bool Calc(int nDestLen,int nSourLen)
	{
		int* pnDest=0;
		BYTE* pbyIndxBusy=0;
	
		if(nDestLen>nSourLen)
		{
			//ошибка
			return false;
		}
	
		//массив для сочетаний индексов
		pnDest=new int[nDestLen];
	
		//для для пометки занятости индексов
		pbyIndxBusy=new BYTE[nSourLen];
		memset(pbyIndxBusy,0,nSourLen);
	
		int inxMax=nSourLen-1;
	
		//индексы == 0...(nSourLen-1)
		//инитное заполнение pnDest
		for(int i=0;i<nDestLen;i++)
		{
			pnDest[i]=i;
			pbyIndxBusy[i]=1;//помечаем - индекс занят
		}
	
		//погнали
		for(;;)
		{
			////////////////////////////////////////////////////
			//ТУТ: 
			//pnDest[nDestLen] - ОЧЕРЕДНОЕ ПРАВИЛЬНОЕ СОЧЕТАНИЕ
			//сохранения результатов нет, надо делать отдельно
			////////////////////////////////////////////////////
	
			//ищем следующее сочетание
			int L,i;
			int nTempInd;
			for(L=nDestLen-1;L>=0;L--)
			{
				nTempInd=pnDest[L];
				//помечаем индекс как незанятый
				pbyIndxBusy[nTempInd]=0;
				
				//увеличиваем индекс, пока не найдём незанятый, либо пока
				//не переполнится
				bool bOverFlow=false;
				for(;;)
				{
					nTempInd++;
					if(nTempInd>inxMax){bOverFlow=true;break;}//переполнение индекса
	
					//смотрим - не занят  ли индекс
					if(!pbyIndxBusy[nTempInd])
					{
						//сохраняем индекс и помечаем как занятый
						pnDest[L]=nTempInd;
						pbyIndxBusy[nTempInd]=1;
						break;
					}
				}
	
				if(bOverFlow)
				{
					//переполнение индекса
					pnDest[L]=0;
	
					//переходим к изменению предыдущего индекса
					continue;
				}
	
				//"левая часть" сочетания найдена. Дописываем "правую часть"
	
				int i1=0;//для поиска незанятых индексов
	
				bool bErr=false;
				L++;
				//ищем незанятые индексы
				for(;L<nDestLen;)
				{
					if(!pbyIndxBusy[i1])
					{
						//записываем индекс
						pnDest[L]=i1;
						//помечаем индекс как занятый 
						pbyIndxBusy[i1]=1;
						//двигаемся правее
						L++;
						continue;
					}
	
					i1++;
					if(i1>=nSourLen){bErr=true;break;}
				}
	
				if(bErr)
				{
					//непонятная ошибка - сюда никогда
					//не должны попасть (по идее...)
					L=0;
					break;
				}
	
				break;
			}
	
			//проверяем на СТОП
			if(L<0) break;
		}
	
		//удаляем временные массивы
		if(pnDest)delete[]pnDest;
		if(pbyIndxBusy)delete[]pbyIndxBusy;
	
		/////////
		return true;
	}
};

//вызов:
if(XXX::Calc(3,7))
{
   //посчитано, но результаты не сохранены
}

[Алексей++]

(заходи в асю , я сейчас онлайн)

вот рабочий код на си++, я вроде протестил.
Ну и , соответственно тебе надо переложить на дельфи..

 там, где
         //ТУТ:
         //pnDest[nDestLen] - ОЧЕРЕДНОЕ ПРАВИЛЬНОЕ СОЧЕТАНИЕ

- в этом месте в буфере pnDest длиной nDestLen - очередная правильная последовательность. Тебе нужно куда-то сохранить её отсюда.
-------------------------------
а вызывать так:
if(XXX::Calc(3,7))
{
   //посчитано, но результаты не сохранены
}
else
{
   //длина буфера меньше количества элементов
}


-----------------------------

вот например у меня в буфере 6 элементов: 0123456, длина комбинации - 4
я первое сочетание беру 0123 и перебираю до 6000? и я так понимаю, еще надо отлавливать, когда повторяются цифры, да? а вот как же это отловить?

ммм... я тебя запутал слегка...

перефразирую цитату "правильно" :

вот например у меня в МАССИВЕ ЭЛЕМЕНТОВ 6 элементов: 0163449, длина комбинации (==длина БУФЕРА) - 4. я первое сочетание беру 0123 и перебираю до 6000?...

[MS]

Litanika, тебе срочно, дня 2 можешь подождать?

[Litanika]

Алексей1153, большое спасибо за код, но у меня не получается переделать его в delphi, ругается, что L используется в for и тогда нельзя L:=L+1 делать (
MS, мне чем быстрее, тем лучше, к понедельнику к обеду надо.

[Алексей++]

Litanika, ну так  -  сделай в

for(; ; )
{
}
просто работу с L продумай, это несложно

L=nDestLen-1
for(; ; )
{
   if(!(L>=0))break;
...
...
   L--;
}


только учти continue - а то (L--) не произойдёт

[Dimka]

Переменное количество вложенных циклов - это признак того, что задачу удобнее решать рекурсивно.

[Алексей++]

dimka, может и удобно, но не люблю я рекурсию Напиши свой вариант - может сразу на дельфи, девушка тебе только спасибо скажет

[Dimka]

Ну, во-первых, это задача не на техническую специфику или на особенности языка программирования, а теоретическая - на развитие навыков программирования, поэтому, как преподаватель, считаю вредным для девушки выдавать для неё готовые решения. Во-вторых, у меня нет под рукой Delphi, чтобы отладить решение; только Borland Pascal 7.0 имеется.

[Litanika]

Всем спасибо, я нашла решение, правда с помощью рекурсии. Кому интересно, в приложении. Тему можно закрыть.