Показать сообщение отдельно
Старый 20.12.2005, 16:52     # 6
Trotil
Advanced Member
 
Аватар для Trotil
 
Регистрация: 21.04.2005
Адрес: град Москва
Сообщения: 431

Trotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собойTrotil Имеются все основания чтобы гордиться собой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 также исправил баг с функцией.

Последний раз редактировалось Trotil; 20.12.2005 в 19:25.
Trotil вне форума