Вариант генерации подмножеств -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [3.147.104.248]

Друзья, соблюдайте, пожалуйста, правила форума и данного раздела:

• Данный раздел не предназначен для вопросов и обсуждений, он содержит FAQ-заготовки для разных языков программирования. Любой желающий может разместить здесь свою статью. Вопросы же задавайте в тематических разделах!
• Если ваша статья может быть перенесена в FAQ соответствующего раздела, при условии, что она будет оформлена в соответствии с Требованиями к оформлению статей.
• Чтобы остальным было проще понять, указывайте в описании темы (подзаголовке) название языка в [квадратных скобках]!

Модераторы: Модераторы

Новое голосование

Вариант генерации подмножеств , [Pascal] для "Комбинаторики"

Romtek

Сообщ. #1 , 24.02.05, 13:09

пропагандист

Профиль · PM

Поощрения: 30 Dgm

Рейтинг (т): 188

Автор: mikv

Вариант генерации подмножеств

Используем двоичное представление. Для перебора всех подмножеств нам необходимо перебрать все числа от 0 до 2ⁿ-1.
Как переходить от текущего двоичного числа к следующему? Можно каждый раз осуществлять перевод из 10-ной системы в 2-чную.
Но там используются крайне медленные операции деления. А почему бы не просто складывать "в лоб" двоичные числа? То есть точно также, как мы делаем на бумажке, складывая обычные числа.
Складываются так:

1+1=0. То есть 0 пишем в текущий разряд, а единичка переносится в следующий.

1+0=1

0+1=1

0+0=0

Если внимательно взглянуть на эту табличку - можно понять, что на самом деле перед нами таблица значений функции XOR.
поэтому мой вариант генерации множеств:

procedure NextSubset;

var

i : Integer;

begin

i := n + 1;

repeat

dec(i);

B[i] := B[i] xor 1;

until B[i]=1;

end;

n - количество элементов в исходном множестве.

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

предлагаю использовать примерно так:

maxk := 1 shl n;

FillChar (B,SizeOf(B),0);

for k := 1 to maxk do

begin

NextSubset;

{Некоторые действия}

end;

Сообщение отредактировано: Jin X - 17.11.16, 15:21

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0175 ] [ 16 queries used ] [ Generated: 25.04.24, 11:24 GMT ]