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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.02.2011, 15:09
Новичок

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

генерация подмножеств заданной размерности в множестве
Здравствуйте.
Необходимо написать метод, получающий на вход размерность подмножеств, а на выходе выдающий эти подмножества.
т.е. есть массив длинны n и надо получить все подмножества длинны к примеру n/2. (1,2) и (2,1) - являются одинаковыми подмножествами и нужно получить только одно, т.е. порядок элементов в подмножестве не учитывается. Желательно бы алгоритм без повторяющихся, иначе при больших n становится очень много мусора.
Помогите плз с алгоритмом.
  #2  
Старый 14.02.2011, 00:24
Новичок

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

Я видимо не совсем в тот раздел форума написал.
Админы, перенесите в "Реализация, исходники, языки", если сочтёте нужным.
  #3  
Старый 14.02.2011, 04:52
гocть

 
Сообщений: n/a

ну можно к примеру тупо рекурсией. полно таких алгоритмов. только не подмножествами это называют, а комбинациями.
подробное иллюстрированное руководство: Кнут, Art of Computer Programming, Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005)
  #4  
Старый 14.02.2011, 04:53
гocть

 
Сообщений: n/a

или сочетаниями
  #5  
Старый 14.02.2011, 22:26
Новичок

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

вы не подскажите, где можно бесплатно скачать эту книгу?
я понимаю, что алгоритмы есть, но вот я пока не одного, нормально объяснённого не встретил.
тупо рекурсией, это в чём она будет заключаться? если это так тупо и алгоритмов полно, то скажите хотя бы один))
по данной ссылке есть несколько кодов, но я не понимаю их синтаксис.
перепишите на что нибудь си-подобное плз, буду оч признателен.
http://www.linux.org.ru/forum/development/3361427

Последний раз редактировалось carlos0n, 14.02.2011 в 22:36.
  #6  
Старый 14.02.2011, 22:52
Новичок

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

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

0 1 2 3 4 5 6 7 - индексы массива

печатаем все подмножества размерности 5
тогда надо распечатывать эл-ты с индексами вида:

0 1 2 3 4
0 1 2 3 5
0 1 2 3 6
0 1 2 3 7
0 1 2 4 5
0 1 2 4 6
............
3 4 5 6 7

думаю алгоритм понятен по примеру.
но я не могу чего то сообразить как это закодить))

Последний раз редактировалось carlos0n, 15.02.2011 в 00:57.
  #7  
Старый 15.02.2011, 11:15
гocть

 
Сообщений: n/a

ну вот к примеру все сочетания из 6 по 3:
Код:
yoda@tatooine:~$ cat p.cc
#include <cstdio>

const int N = 6, K = 3;
int a[K];

void rec(int i)
{
    if (i == K) {
        for (int j = 0; j < K; j++)
            printf("%d ", a[j]);
        printf("\n");
    } else {
        for (a[i] = (i > 0 ? a[i-1] + 1 : 1); a[i] < N; a[i]++)
            rec(i + 1);
    }
}

int main()
{
    int a[N];
    rec(0);
}
yoda@tatooine:~$ ./p
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5
  #8  
Старый 15.02.2011, 11:17
гocть

 
Сообщений: n/a

Поправка:
Код:
        for (a[i] = (i > 0 ? a[i-1] + 1 : 1); a[i] <= N; a[i]++)
Код:
1 2 3 
1 2 4 
1 2 5 
1 2 6 
1 3 4 
1 3 5 
1 3 6 
1 4 5 
1 4 6 
1 5 6 
2 3 4 
2 3 5 
2 3 6 
2 4 5 
2 4 6 
2 5 6 
3 4 5 
3 4 6 
3 5 6 
4 5 6
  #9  
Старый 15.02.2011, 14:44
Новичок

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

спасибо большое! очень мне помогли!
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Наименьшая сумма от 2-х точек до заданной. daishell Вычислительная геометрия 3 19.12.2008 10:56
Построение отрезков в большом множестве Денис Вычислительная геометрия 1 12.07.2008 22:18
[C++] Найти все вершины графа, к которым существует путь заданной длины ALI Реализация, исходники, языки 0 11.05.2008 20:00
Нахождение максимально заданной точки Skylan Вычислительная геометрия 3 12.01.2008 17:02
генерация текста как? незарегистрированный Реализация, исходники, языки 0 20.11.2006 11:20