Задача с 1С связана чуть менее чем ничего. Но я знаю, что здесь собираются талантливые люди, у которых всегда можно спросить совета. Есть задача по проведению турнира по швейцарской системе проведения турниров.
Не могу найти оптимальный способ поиска "ранее не игравших пар". Поконкретнее:
На входе имеем Список (массив) Людей размером ВсегоЛюдей (всегда четное) в каком либо туре. До этого было какое-то количество туров, где некоторые из этих людей могли играть между собой. Задача: разбить этот массив на пары так, чтобы ни одна из пар не играла ранее.
Например, имеем 6 человек {1,2,3,4,5,6}. В первом туре были проведены встречи:
1-2, 3-4, 5-6
Во втором:
1-4,2-5,3-6
Над составить пары на Третий тур, причем уже сыгравшие комбинации надо исключить.

Есть идеи? У меня одни тупые переборы в голове мелькают.

В одном туре один человек участвует 1 раз?

berezdetsky писал(а) 21. Мая 2010 :: 11:51:

Да

JohnyDeath писал(а) 21. Мая 2010 :: 12:50:

Тогда в один проход задача не решается, нужен какой-то оптимизирующий алгоритм.
Т.е., к примеру, 1-6, 2-3, 4-5 - допустимое решение, а 1-3, 2-4, ?-? - нет.

Рекомендую Microsoft Solver Foundation.  

Ну или перебор, если данных не слишком много..

---

Да, просто список доступных пар можно получить так:

declare @люди table (id integer)

insert into @люди values (1)
insert into @люди values (2)
insert into @люди values (3)
insert into @люди values (4)
insert into @люди values (5)
insert into @люди values (6)

declare @турниры table (id integer, чел1 integer, чел2 integer)

insert into @турниры values (1, 1, 2)
insert into @турниры values (1, 3, 4)
insert into @турниры values (1, 5, 6)
insert into @турниры values (2, 1, 4)
insert into @турниры values (2, 2, 5)
insert into @турниры values (2, 3, 6)

select люди1.id чел1, люди2.id чел2
from @люди люди1
	inner join @люди люди2 on люди1.id < люди2.id
where not люди2.id in (
		select чел2
		from @турниры
		where чел1 = люди1.id
	) 

вот наваял вариантик у меня получается 21 игра для 6 игроков. Не знаю насколько правильно.
Исходные данные:

create table #players (id int primary key,name varchar(50))
create table #games(id int identity primary key,player1 int,player2 int)


insert into #players values(1,'Иванов')
insert into #players values(2,'Петров')
insert into #players values(3,'Сидоров')
insert into #players values(4,'Пупкин')
insert into #players values(5,'Ступкин')
insert into #players values(6,'Рабинович')
 

Поиск пары:

declare @p1 int,@p2 int

select top 1
 @p1 = vt.p1,@p2 = vt.p2
from(
select distinct
 case when p.id > p2.id then p.id else p2.id end p1,
 case when p.id < p2.id then p.id else p2.id end p2
from #players p cross join #players p2) vt
left join
 #games g on g.player1 = vt.p1 and g.player2 = vt.p2 or g.player2 = vt.p1 and g.player1 = vt.p2
where
 g.id is null

if @p1 is null
	print 'Вариантов больше нет'
else
	insert into #games values(@p1,@p2)
 

berezdetsky писал(а) 21. Мая 2010 :: 13:04:

Даже примерно не знаю что это такое   Даже если это и отличное решение, то что-то мне подсказывает, что я времени убью больше, чем надо

berezdetsky писал(а) 21. Мая 2010 :: 13:04:

Вот какой перебор ты бы сделал. Ведь тут надо в случае "неудачи" возвращаться на несколько шагов назад, т.е. если мы подобрали 3 пары из 4-х, а 4-я пара уже играла между собой, то надо возвращаться назад и переставлять что-то, чтобы получился новый набор, ну и запомнить, какие наборы мы уже просмотрели...
{я понятно изъясняюсь? а то у меня всё как-то параллельно навалилось и в голове каша, поэтому не судите строго}

JohnyDeath писал(а) 21. Мая 2010 :: 13:25:

Четыре перебора, последовательно:

• получить все возможные пары;
• получить все возможные турниры;
• получить все наборы непересекающихся турниров;
• найти самый длинный набор турниров.

Как-то так..

JohnyDeath писал(а) 21. Мая 2010 :: 11:43:



ид пары это 2 в степени ид игрока

1 = 2
2 = 4
3 = 8
4 = 16
5 = 32
6 = 64

складываем пары между собой получем = ид пары
ид пары не должен быть равен ид игрока (что бы игрок не играл сам с собой  )