Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Вывод всех перестановок k элементов из множества N имеющихся [D7]

Страницы: < 1 2 3 >
ННН © (2012-10-28 23:00:00)
Всем привет нужен алгоритм (любой на словах или кодом) выводящий все перестановки k элементов (не повторяющихся) из множества N имеющихся.
т.е. Пусть N=6, {1,2,3,4,5,6}, k=4
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
и т.д.

Sha (2012-10-31 14:09:00) [21]
> ННН (31.10.12 11:32) [22]

Вероятно, ты о варианте (TStringList,Sorted=true,Duplicates=dupIgnore),
который тебе предложили на другом форуме.

Я бы не назвал это ни решением, ни помощью.

Sha (2012-10-31 13:45:00) [22]
> Romkin © (30.10.12 15:57) [20]

у Липского та же ошибка, алгоритм 1.16 не работает при n=k>1

ННН (2012-10-31 11:32:00) [23]
всем большое спасибо за участие) всё получилось с помощью одного человека)

Sha (2012-10-30 21:06:00) [24]

> Romkin © (30.10.12 15:57) [20]

похоже, что первый приведенный алгоритм не работает при n=k

Romkin (2012-10-30 15:57:00) [25]
http://forum.sources.ru/index.php?showtopic=330364

QAZ5 (2012-10-30 15:42:00) [26]
главное не путать теплое с мягким

Sha (2012-10-30 11:12:00) [27]
> han_malign (30.10.12 10:23) [17]

автор не путает, он все правильно понимает: один из способов перечисления размещений состоит в использовании перестановок и сочетаний, а именно во всевозможных перестановках элементов каждого сочетания

han_malign (2012-10-30 10:23:00) [28]

> это число сочетаний а не всех возможных перестановок!! не путайте ))

- вот и не путайте, то у вас перестановки, то сочетания, а может все-таки - размещения??? Вы уж определитесь...

Sha (2012-10-29 19:26:00) [29]
что мешает? см. [1],[2],[3],[9],[11]

ННН (2012-10-29 19:16:00) [30]
вот есть код, (делает всевозможные перестановки символов строки) надо его переделать под заданную задачу выводить перестановки по К элементов

procedure TForm1.Button1Click(Sender: TObject);
var
sl :TStringList;

procedure Gen(S0,S1 : string); //S1 - 2
var
i :integer;
begin
if length(S1) > 1 then //Возвращает число элементов в массиве или строке
for i:=1 to length(S1) do
Gen(S0+S1[i],copy(S1,1,i-1) + copy(S1,i+1,length(S1)))
//copy создает новую строку из части существующей строки
//имя строки
//с этого элемента
//+ столько элементов
else
sl.Add(S0+S1); //Добавляет данную строку в список, возвращая ее позицию в списке (начинается с 0).
end;

//ген(0, (1,2) )
//2>1
//от 1 до 2 Ген(1,2), Ген()

begin
sl:= TStringList.Create; // Определение объекта списка строк, и указание нашей переменной на него
sl.Sorted:= True; //Когда true, все строки будут добавляться в свою позицию отсортированной последовательности.
sl.Duplicates:= dupIgnore; //dupIgnore Игнорирует (отбрасывает) дубликаты
Gen('',Edit1.Text); //S0 =0, S1 = Edit1.Text
ListBox1.Items.Assign(sl); //Метод Assign Заменяет текущий список содержанием другого списка.
sl.Free ; //просто очистит список и строки
ShowMessage(IntToStr(Form1.ListBox1.Items.Count));
end;

end.

Sha (2012-10-29 19:16:00) [31]
зачем что-то там переводить, проще самому написать несколько строчек

ННН (2012-10-29 18:29:00) [32]
это число сочетаний а не всех возможных перестановок!! не путайте ))
вот я нашёл код того что нужно, можете там посмотреть, единственное что я не шарю в С++, может кто нибудь сможет перевести на делфи ?
http://pastebin.com/ggzJ2dcB

QAZ5 (2012-10-29 17:30:00) [33]
число перестановок равно факториалу числа цифр

Sha (2012-10-29 17:28:00) [34]
исходной перестановке индексов:
1234
соответствуют 15 перестановок твоих элементов,
это в точности все предварительно сгенерированные сочетания:
1) 1234
2) 1235
3) 1236
4) 1245
5) 1246
6) 1256
7) 1345
8) 1346
9) 1356
10) 1456
11) 2345
12) 2346
13) 2356
14) 2456
15) 3456

ННН (2012-10-29 17:06:00) [35]
> т.е. Пусть N=6, {1,2,3,4,5,6}, k=4
> 1 2 3 4
> 1 2 3 5
> 1 2 3 6
> 1 2 4 5
> 1 2 4 6
> 1 2 5 6
> 1 3 4 5

тут будет не 15 перестановок!
если допустим 3 по 2
12
13
21
23
31
32

Sha (2012-10-29 15:14:00) [36]
> ННН (29.10.12 12:00) [6]
> не совсем)

1. Заранее генерием все упорядоченные сочетания из n по k (в нашем случае их будет ровно 15 штук). Для правильной работы алгоритма важно, чтобы элементы в каждом сочетании были одинаково упорядочены (по возрастанию или убыванию).

2. Генерируем очередную перестановку четырех чисел. Но это не перестановка твоих элементов, это просто перестановка четырех последовательных чисел - номеров позиций (индексов). Во вложенном цикле генерируем 15 перестановок твоих элементов, соответствующих только что полученной перестановке индексов. Для этого пробегаемся по всем сочетаниям и подменяем полученные индексы элементами на соответствующих местах в очередном сочетании.

Если остались неясности, спрашивай.

oldman (2012-10-29 13:50:00) [37]
Или 1 2 3 4 = 1 3 4 2 ???

oldman (2012-10-29 13:49:00) [38]

> т.е. Пусть N=6, {1,2,3,4,5,6}, k=4
> 1 2 3 4
> 1 2 3 5
> 1 2 3 6
> 1 2 4 5
> 1 2 4 6
> 1 2 5 6
> 1 3 4 5

Таки 1 3 4 2 !!!

ННН (2012-10-29 12:00:00) [39]
не совсем)

Sha (2012-10-29 07:20:00) [40]
а как у меня реализовано тебе понятно?

Страницы: < 1 2 3 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »