VPF::Генерирование k-элементных подмножеств

Elfet

Дата 17.2.2006, 19:21 (ссылка)

(нет голосов)

Загрузка ...

Белый и Пушистый

Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16

Генерирование k-элементных подмножеств. Прошу помощи! Нужен какой-нибудь алгоритм. Заранее спасибо за ответ (липский-не помог)

--------------------

PHP Чат Скрипт

SoWa

Дата 17.2.2006, 21:21 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Можно вкратце узнать, что это такое?
Просто я может знаю ответ, но называю их по другому.

--------------------

Всем добра smile

Elfet

Дата 17.2.2006, 22:16 (ссылка)

(нет голосов)

Загрузка ...

Белый и Пушистый

Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16

Мммм

А другого названия и нет smile

Нужно их множества размером N получитьь все возможные подмножества размера K smile

--------------------

PHP Чат Скрипт

maxim1000

Дата 18.2.2006, 04:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

сначала выбираем первый элемент (N способов)
а потом - из остальных (N-1) выбираем (K-1) подмножества и прикрепляем к ним выбранный элемент
чтобы избавиться от вариантов, которые отличаются только порядком следования, следующее множество можно выбирать только из элементов, идущих после предыдущего...

--------------------

qqq

Elfet

Дата 18.2.2006, 18:23 (ссылка)

(нет голосов)

Загрузка ...

Белый и Пушистый

Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16

maxim1000, ничего не понял smile

--------------------

PHP Чат Скрипт

SoWa

Дата 18.2.2006, 20:28 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Я тоже, если честно.
Определение скажите!

--------------------

Всем добра smile

maxim1000

Дата 18.2.2006, 20:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

A+b - множество A с добавленным элементом b
A-b - множество A без элемента b
A[n] - n-й элемент множества A
Length(A) - количество элементов A
print(A) - вывести множество

далее - схематически на языке смутно напоминающем C++:

Код


void f(set A,int k,set prefix=0)
{
  if(k==0)
    print(prefix);
  else
    for(int c=0;c<Length(A);c++)
      f(A-A[c],k-1,prefix+A[c]);
}

Добавлено @ 20:47
только этот способ будет выдавать слишком много результатов : и abc, и acb, и bac, ...
чтобы порядок не учитывался, можно сделать так:

Код


void f(set A,int k,set prefix=0,int min=0)
{
  if(k==0)
    print(prefix);
  else
    for(int c=min;c<Length(A);c++)
      f(A,k-1,prefix+A[c],c+1);
}

--------------------

qqq

SoWa

Дата 18.2.2006, 21:12 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Понял! Зачем надо было так сложно называть?

--------------------

Всем добра smile

Elfet

Дата 18.2.2006, 21:20 (ссылка)

(нет голосов)

Загрузка ...

Белый и Пушистый

Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16

А это через рекурсию smile

А я тут узнал, что это алгоритм через цыклы можно и нада smile

Взял книжечку "Комбинаторика для программиста" Липского, нашёл нужный алгоритм(даже два): в первом явный ляп,а второй ну очень запутан smile

--------------------

PHP Чат Скрипт

SoWa

Дата 18.2.2006, 21:27 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Да сам напиши! Все проще некуда!

--------------------

Всем добра smile

maxim1000

Дата 18.2.2006, 21:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

Цитата(SoWa @ 18.2.2006, 20:12

)

Понял! Зачем надо было так сложно называть?

иногда на меня находит какое-то "сложновысказывание"
смотрю, что написал, вижу, что непонятно, пытаюсь пояснить, получается еще запутаннее smile

--------------------

qqq

Elfet

Дата 18.2.2006, 22:51 (ссылка)

(нет голосов)

Загрузка ...

Белый и Пушистый

Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16

не получаеться smile

--------------------

PHP Чат Скрипт

maxim1000

Дата 19.2.2006, 00:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

Цитата(Elfet @ 18.2.2006, 21:51

)

не получаеться

что именно?

--------------------

qqq

esperant0

Дата 19.2.2006, 01:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

1)Cгенирирую случайную выборку к элементов из n.

2)повтори первый этап 10nlog n раз

--------------------

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

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

maxim1000

Дата 19.2.2006, 01:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

Цитата(esperant0 @ 19.2.2006, 00:02

)

10nlog n

а, если не секрет, откуда это значение?

P.S.
насколько я понял, всех выборок не получится
(хотя бы потому, что с некоторой вероятностью все сгенерированне выборки будут одинаковыми)
впрочем, формально это и не требовалось...
Добавлено @ 01:12
а, кстати, вот еще один способ - без рекурсии:
генерируем первую выборку - просто первые K элементов множества
а потом "инкрементируем" ее:
(пусть само множество - числа от 1 до N, в другом случае можно сопоставить элементам их номера)
берем последний элемент и увеличиваем его на 1
если увеличивать некуда - увеличиваем предыдущий на 1, а этот ставим сразу после него
с предыдущим - то же самое, т.е. если его некуда увеличивать увеличиваем предыдущий
и т.д., пока не получим выборку из последних K элементов...
Добавлено @ 01:20
приблизительно

Код


void PrintSet(int *set,int length);//распечатывает набор чисел
bool IncrementSet(int *set,int K,int N)
{
  if(set[0]==N-K)
    return false;
  //считаем, сколько элементов уже достигли максимума
  int c=0;
  while(set[K-c-1]==N-c-1)
    ++c;
  ++set[K-c-1];
  while(c>0)
  {
    set[K-c]=set[K-c-1]+1;
    ++c;
  }
  return true;
}
void PrintAllSubSets(int K,int N)
{
  int *subset=new int[K];
  for(int c=0;c<K;++c)
    subset[c]=c;
  while(true)
  {
    PrintSet(subset,K);
    if(!IncrementSet(subset,K,N))
      break;
  }
}

--------------------

qqq

Elfet

Дата 20.2.2006, 23:34 (ссылка)

(нет голосов)

Загрузка ...

Белый и Пушистый

Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16

Хех

Волот весь код то!! smile

Из Липского:

Код


    int *a = new int[k+1];

    int i,p;

    for( i=1; i<=k; i++ )
        a[i] = i;

    p = k;

    while( p >= 1 )
    {
        my_out(a,k);
        if( a[k] == n ) 
            p = p - 1;
        else
            p = k;
        if( p >= 1)
            for( i=k; i>=p; i-- )
            {
                a[i] = a[p] + i - p + 1;

            }
            
    }

--------------------

PHP Чат Скрипт

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »