IMHO.WS - Програмка отбора множеств

IMHO.WS (http://www.imho.ws/index.php)

- Программирование (http://www.imho.ws/forumdisplay.php?f=40)

- - Програмка отбора множеств (http://www.imho.ws/showthread.php?t=97551)

Програмка отбора множеств

Ребята,помогите пожалуйсто написать такую програмку на любом языке:

Даны 25 букв: A,B,C,D,E,F,G,H,I,K,L,M,N,O,P,Q,R,S,T,U,V,W,Y,J,Z
и 21 переменная, которым присвoены следующие наборы букв
X1 = {A,B,C,D,E,F,G,H,I,K}
X2 = {L,M,N,O,P}
X3 = {Q,R,S,T,U,V,W,Y,J,Z}
X4 = {A,B,L,M,Q,R}
X5 = {C,D,E,F,G,H,I,K,N,O,P,S,T,U,V,W,Y,J,Z}
X6 = {A,L,Q}
X7 = {B,M,R}
X8 = {L,Q,R,T,W}
X9 = {A,M,S,U,Y}
X10= {B,C,N,V,J}
X11= {D,E,F,G,H,I,K,O,P,Z}
X12= {A,B,D,G,L}
X13= {C,E,H,M,Q}
X14= {F,I,N,R,S}
X15= {K,O,P,T,U,V,W,Y,J,Z}
X16= {L}
X17= {A,Q}
X18= {B,M,R}
X19= {C,D,S,T}
X20= {E,G,N,U,W}
X21= {F,H,I,K,O,P,V,Y,J,Z}

1)Необходимо отобрать все комбинации из переменных(ограничим количество иксов в одной комбинации до 10), которые содержат все заданные буквы(буквы могут повторяться).
Например Х1,Х2 и Х3 содержат все буквы, или Х2,Х17,Х18,Х19,Х20 и Х21( в этом случае буквы повторяются, но это допустимо)

2)Теперь каждой из Х присваивается какое либо число(1<n<10), и нужно оставить только те из отобраных комбинаций, которые
удовлетворяют неравенству 1/Х1 + 1/Х2 +,...,+ 1/Хn < 1, где Х1,Х2,..,Хn - переменные в 1) отобраных комбинаций.
например:
Х1=2, Х2=3, Х3=4, Х17=10, Х18=7, Х18=20, Х19=8, Х20=15, Х21=6

смотрим: 1/2 + 1/3 +1/4 = 1.0833 => не подходит,(Х1,Х2,Х3)

1/3 + 1/10 + 1/7 + 1/8 + 1/15 + 1/6 = 0.93 => подходит(Х2,Х17,Х18,Х19,Х20,Х21)

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

Alexk1984, простите, а в чем собственно ваша проблема в этой задаче?

Trotil, в том что я не программирую, но мне очень нужна эта программка, и не к кому обратиться,
поэтому я и прошу помощи,
можно узнать, насколько сложно и обширно решение этой задачки?

Цитата:

Alexk1984:
можно узнать, насколько сложно и обширно решение этой задачки?

ИМХО, программа, которую может написать любой человек, прослушавший хотя бы полсеместра программирования на любом языке.

Цитата:

Alexk1984:
Ребята,помогите пожалуйсто написать такую програмку на любом языке:

Отпимальней, наверное, будет писать на Паскале, т.к. там есть тип данных множество. У Си есть std::set, как аналог, но все же это не является встроенным средством языка.

Цитата:

Alexk1984:
Trotil, в том что я не программирую, но мне очень нужна эта программка

Тогда, извините, полностью писать програаму совершенно нет времени. Я спросил, хотел подсказать трудноподдающиеся участки кода, но в твоем случае, они к сожалению, не помогут.

Хорошо, я понимаю

Я пытался начинать писать её в паскале, но с самого начала загвоздка,
как сформировать все возможные комбинации из иксов(мах.десятизначные)?

Так. Мысли такие: (есть привычка делать код универсальным,а создание 21 переменной и, например 10 влояженных циклов - кажется дикостью...), поэтому:

1) загоним 21 переменную в множество-массив:

Код:

 

type 

   charset = set of 'A'..'Z';

var 

   charsetarray = array [0..21] of charset;

   maxset : charset;

2) В начале программы инициализируем:

Код:

 maxset = ['A','B','C', ..., 'Z'];

 charsetarray [0] :=[]; (так надо)

 charsetarray [1] := ['A','B','C','D','E','F','G','H','I','K']

 charsetarray [2] := [...]

3) вот алгоритм для нахождения всех подмножеств мощности k, из множества мощности n:

Цитата:

Воспользуемся следующим алгоритмом генерации сочетаний по k элементов из множества A:

В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число k). В качестве начальной конфигурацией возьмем следующую: B[j]=j, j=1,...,k.
Ищем B[j] с максимальным индексом j такое, что
B[j]<n+j-k,
увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значениями элементов массива B[m], m>j, последний элемент B[k] не превосходил бы n). Если такого B[j] не существует, то генерация сочетаний для данного k закончена.

Кода под этот алгоритм не нашел. (хотя он будет генерить только нужные нам комбинации)
Но есть способ проще, хотя он будет работать значительно дольше (много лишних комбинаций).
Основная идея - комбинацию будем представлять обычным целым числом, где i-тый бит будет означать отстутствие/присутствие i-той переменной в комбинации:
пример: 10 = (1010) в двоичном виде - означает комсбинацию, в которую входит 2-ая и 4-ая переменная

в цикле от 1 до (2^21-1) мы должны послать эту переменную (i) в процедуру, которая:
1) посчитает количество единиц в двоичном наборе (гаденькое ограничение на 10 переменных в комбинации) - см. функцию внизу.
2) если проходит проверку, то

Код:

(charsetarray [1*((2^0 and i) shr 0)] + 

 charsetarray [2*((2^1 and i) shr 1)] + 

 charsetarray [3*((2^3 and i) shr 2)] + ... + 

 charsetarray [21*((2^21 and i) shr 21)]  = maxset)

- если это выражение истинно, то комбинация годится.
2^k and i - побитовое умножение i и k-того бита - возвращает 0, если нет k - того бита в множеств, а charsetarray[0] - это у нас пустое множество, ни на что не влияющее.
В случае совпадения там будет возвращено 2^k, в то время как там нужно получить в качестве индекса целое число k. Для этого происходит сдвиг на k разрядов вправо, в результате чего (k+1)-тая единица сдвинется на (k) разряд вправо и выражение станет равным единице, a k*1=k, что и требовалось получить.

И наконец, простая функция подсчета единиц в двоичном представлении числа i:

Код:

function func (m:longint) : integer;

var 

 n,c : Integer;

begin 

 c:=0;

for n:=0 to 21 do begin

  inc(c, m mod 2);

  m := m shr 1;

  end;

 func := c;

end;

Цитата:

а когда мы указывали charsetarray = array [1..21] of charset;, следует внести 0 или оно и так определит его как пустое множество?

Исправил, a также исправил баг с функцией.

а когда мы указывали charsetarray = array [1..21] of charset;, следует внести 0 или оно и так определит его как пустое множество?

В общем получилось такое):

Код:

type charset = set of 'A''B''C''D''E''F''G''H''I''K''L''M''N''O''P''Q''R''S''T''U''V''W''Y''J''Z';

var charsetarray = array [0..21] of charset;

    maxset : charset;



begin

maxset = ['A','B','C','D','E','F','G','H','I','K','L','M','N','O','P','Q','R','S','T','U','V','W','Y','J','Z'];

charsetarray [0] := [];

charsetarray [1] := ['A','B','C','D','E','F','G','H','I','K'];

charsetarray [2] := ['L','M','N','O','P']

charsetarray [3] := ['Q','R','S','T','U','V','W','Y','J','Z'];

charsetarray [4] := ['A','B','L','M','Q','R'];

charsetarray [5] := ['C','D','E','F','G','H','I','K','N','O','P','S','T','U','V','W','Y','J','Z'];

charsetarray [6] := ['A','L','O'];

charsetarray [7] := ['B','M','R'];

charsetarray [8] := ['L','Q','R','T','W'];

charsetarray [9] := ['A','M','S','U','Y'];

charsetarray [10] := ['B','C','N','V','J'];

charsetarray [11] := ['D','E','F','G','H','I','K','O','P','Z'];

charsetarray [12] := ['A','B','D','G','L'];

charsetarray [13] := ['C','E','H','M','Q'];

charsetarray [14] := ['F','I','N','R','S'];

charsetarray [15] := ['K','O','P','T','U','V','W','Y','J','Z'];

charsetarray [16] := ['L'];

charsetarray [17] := ['A','Q'];

charsetarray [18] := ['B','M','R'];

charsetarray [19] := ['C','D','S','T'];

charsetarray [20] := ['E','G','N','U','W'];

charsetarray [21] := ['F','H','I','K','O','P','V','Y','J','Z'];





charsetarray [1*((2^0 and i) shr 0)] +

charsetarray [2*((2^1 and i) shr 1)] +

charsetarray [3*((2^3 and i) shr 3)] +

charsetarray [4*((2^4 and i) shr 4)] +

charsetarray [5*((2^5 and i) shr 5)] +

charsetarray [6*((2^6 and i) shr 6)] +

charsetarray [7*((2^7 and i) shr 7)] +

charsetarray [8*((2^8 and i) shr 8)] +

charsetarray [9*((2^9 and i) shr 9)] +

charsetarray [10*((2^10 and i) shr 10)] +

charsetarray [11*((2^11 and i) shr 11)] +

charsetarray [12*((2^12 and i) shr 12)] +

charsetarray [13*((2^13 and i) shr 13)] +

charsetarray [14*((2^14 and i) shr 14)] +

charsetarray [15*((2^15 and i) shr 15)] +

charsetarray [16*((2^16 and i) shr 16)] +

charsetarray [17*((2^17 and i) shr 17)] +

charsetarray [18*((2^18 and i) shr 18)] +

charsetarray [19*((2^19 and i) shr 19)] +

charsetarray [20*((2^20 and i) shr 20)] +

charsetarray [21*((2^21 and i) shr 21)] = maxset



function func (m:longint) : integer;

n,c : integer;



begin

c:=0;

for n:=0 to 21 do begin

 inc(c, m mod 2);

 m := m shr 1;

 end;



 func := c;



 end;

но Freepascal сразу же в третьей строке выдаёт ошибку, вроде всё правильно, не знаю почему.

Извините за назойливость, но это действительно моя первая программа ( точнее ваша)).

Мама - мия.. Только вот не надо было все тупо копировать, тот код, который я привел - это примерно треть программы... Мдя...
Потом местами - это не совсеи по правилам Паскаля написано, что впрочем легко исправляется...

Предпологалось, что хоть некоторые сведения о программировании у вас имеются..

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

Ну теперь уже что-то имеется..))
можно вопросик,
Вы составите её теперь полностью или мне продолжать самостоятельно освоение Паскаля)?

Задачка решена, спасибо всем са помощь!!