Так. Мысли такие: (есть привычка делать код универсальным,а создание 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 также исправил баг с функцией.