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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.12.2012, 19:19
Пользователь

Отправить личное сообщение для blackbanny Посмотреть профиль Найти все сообщения от blackbanny
 
Регистрация: 05.01.2011
Сообщений: 29

составление n-элементных множеств из массива
Доброго времени суток!
пишу скрипт и понадобилось составлять n-элементные множества.
суть в том, что в функцию передается массив и число, которое обозначает длину множества, на выходе получаем список множеств заданной длинны.
ПРИМЕР:
массив: [a, b, c, d]
число: 2
результат функции: a,b; a,c; a,d; b,c; b, d; c,d;

подскажите алгоритм или псевдокод для реализации функции.
  #2  
Старый 14.12.2012, 09:34
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Это называется сочетания (combination)
Здесь на сайте есть общее описание. Реализация наверняка в форуме имеется.
Кроме того, см.
http://e-maxx.ru/algo/generating_combinations

А проще всего (не самый эффективный, но это не всегда имеет значение) рекурсивный алгоритм
Код:
procedure Combine(Array, StartIndex, CountLeft, Combination)
  if CountLeft = 0 then
    вывести Combination
  else
    for i := StartIndex to Length(Array) - CountLeft do
        Combine(Array, i + 1, CountLeft - 1, Combination + Array[i])

Последний раз редактировалось MBo, 14.12.2012 в 09:36.
  #3  
Старый 19.12.2012, 18:58
Пользователь

Отправить личное сообщение для blackbanny Посмотреть профиль Найти все сообщения от blackbanny
 
Регистрация: 05.01.2011
Сообщений: 29

MBo, спасибо)
нашел такую реализацию на C:
Код:
#include <stdio.h>
 
const int numVal = 5;
const int setSize = 3;
const char data[numVal] = { 'a', 'b', 'c', 'd', 'e' };
 
 
void Print( int value )
{
    int numPrn = 0;
    for (int i = 0; i < numVal; ++i) {
        if (value & (1 << i)) {
            printf("%c", data[i]);
            printf((++numPrn < setSize) ? ", " : "\n");
        }   
    }   
}
 
void Place( int value, int offs, int num )
{
    int i, limit = numVal - offs;
    for (i = 0; i < limit; ++i) {
        int offs2 = offs + i;
        int value2 = value | (1 << offs2);
        int num2 = num + 1;
        if (num2 < setSize) 
            Place(value2, offs2 + 1, num2); 
        else 
            Print(value2);
    }
}
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Требуется составление алгоритма Работа Работа 3 11.12.2008 08:31
Перебор элементов прямого произведения множеств Илья Марков Математические алгоритмы 1 02.07.2008 21:00
теория множеств Mayor Реализация, исходники, языки 0 14.09.2007 11:15
Составление расписания турниров KBEHTuH Сортировка и поиск 2 27.06.2007 07:05
Составление расписания туров.. KBEHTuH Задачи 2 30.05.2007 18:28