VPF::Алгоритм составления всех возможных сочетаний

Alenka_

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

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

Загрузка ...

Шустрый

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

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

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

Например: есть числа - 11, 9, 7, 5, 3

задаем количество чисел в сочетаниях =2,
получаем:
11, 9
11, 7
11, 5
11, 3
9, 7
9, 5
9, 3
7, 5
7, 3
5, 3

задаем количество чисел в сочетаниях =3,
получаем
11, 9, 7
11, 9, 5
11, 9, 3
11, 7, 5
11, 7, 3
11, 5, 3
9, 7, 5
9, 7, 3
9, 5, 3
7, 5, 3

Эти числа можно хранить в двумерном масссиве, а можно в ArrayList, состоящий из ArrayList...(в java). Как лучше?

Поиском посмотрела темы, которые тут есть, нашла, что, вроде можно решить рекурсией...
Но что-то не соображу, как ее тут применить. Да и может другие методы есть?

Sardar

Дата 16.2.2008, 23:17 (ссылка)

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

Загрузка ...

Бегун

Профиль
Группа: Модератор
Сообщений: 6986
Регистрация: 19.4.2002
Где: Нидерланды, Groni ngen

Репутация: 1
Всего: 317

На haskell:

Код


-- исключаем пустые сорцы и ограничиваем рекурсию
powset [] n = []
powset set 0 = []
-- специальный случай - комбинации с 1 элементом
powset set 1 = map (\x -> [x]) set
-- сняли powset меньшего порядка, добавили свой элемент, продолжили с остатком множества
powset (x:xs) n = (map (\a -> x:a) (powset xs (n-1))) ++ (powset xs n)

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

Опыт - сын ошибок трудных © А. С. Пушкин
Процесс написания своего велосипеда повышает профессиональный уровень программиста. © Opik
Оценить мои качества можно тут.

Alenka_

Дата 17.2.2008, 02:13 (ссылка)

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

Загрузка ...

Шустрый

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

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

Красиво, конечно, но непонятно...

Nestor

Дата 18.2.2008, 17:50 (ссылка)

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

Загрузка ...

Новичок

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

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

Alenka_. Вот мой алгоритм. Чтоб код стал java-совместимым нужно лишь заменить функции вывода на соответствующие и немного подредактировать оформление.

Код


#include <cstdlib>
#include <iostream>

#define NumsOfElems 4
#define NumsOfValues 7

using namespace std;

void recursion(int, int, int);

int elems = NumsOfElems;
int arr[NumsOfValues];
int arr_of_values[NumsOfValues]={0,1,2,3,4,5,6 /*,...*/};

int main(int argc, char *argv[])
{
    recursion(0,NumsOfValues - NumsOfElems +1,0);
    return EXIT_SUCCESS;
}

void recursion(int min, int max, int rec){

    for(int i=min; i < max; i++){
        arr[rec] = i;
        if(rec == elems -1){
            for(int m = 0; m < elems; m++){
                cout << arr_of_values[arr[m]] <<" ";
            }
            cout << endl;
            continue;
        }
        if(i==max) break;
        recursion(i+1, max+1, rec+1);
    }
}

Alenka_

Дата 18.2.2008, 23:45 (ссылка)

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

Загрузка ...

Шустрый

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

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

Урраа!!! Работает! smile

Nestor, Спасибо большое!! Тебе плюс от меня.
Только... у тебя этот код работает? Там же выход индекса за предел возможен. Нужно проверку одну включить.

Вот мой код:

Код


void recursion(int min, int max, int rec){
        if (rec >= elems) return;
        for(int i = min; i < max; i++){
            arr[rec] = i;
            if(rec == elems - 1){
                for(int m = 0; m < elems; m++){
                    System.out.println( arr_of_values[ arr[ m ] ] + " " );
                }
                System.out.println(" ");
            }
            if( i >= max ) return;
            recursion(i + 1, max + 1, rec + 1);
        }
    }

Ой... а мне нельзя репутацию повышать... попрошу модераторов

Это сообщение отредактировал(а) Alenka_ - 18.2.2008, 23:46

Kangaroo

Дата 18.2.2008, 23:56 (ссылка)

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

Загрузка ...

AA - Aussie Animal

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

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

Цитата(Alenka_ @ 18.2.2008, 22:45

)

Ой... а мне нельзя репутацию повышать... попрошу модераторов

Мы и без них справимся, не будем тревожить грозных модеров smile

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

Lost....

Alenka_

Дата 18.2.2008, 23:59 (ссылка)

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

Загрузка ...

Шустрый

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

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

Kangaroo, Спасибо! smile

Nestor

Дата 19.2.2008, 17:17 (ссылка)

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

Загрузка ...

Новичок

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

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

Kangaroo, Спасибо за посредничество. smile

Alenka_, пожалуйста.

Цитата(Alenka_ @ 18.2.2008, 23:45

)

Только... у тебя этот код работает? Там же выход индекса за предел возможен. Нужно проверку одну включить.

Хмм... Все работает. Только, похоже, я допустил одну ошибочку: размер массива arr - NumsOfElems или elems. Но это при выполнении незаметно, поскольку NumsOfValues всегда больше NumsOfElems.
А... У вас мой вариант не работает из-за плохого с++->java переводчика smile

У меня:

Код


            cout << endl;
            continue;

У вас:

Код


        System.out.println(" ");

Тут continue возвращает нас в цикл, откуда при проверки мы сразу выходим, логичней было написать return; Т.е. в моем случае функция лишний раз и вовсе не вызывается. Насчет этого

Код


if(i==max) break;

То это никогда не наступает - смело можно удалять эту строку. Моя вторая очепатка. smile

Alenka_

Дата 20.2.2008, 01:19 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата

из-за плохого с++->java переводчика

ну вот, охарактеризовали... smile

Насчет размера массива и той строки ты прав. А вот return нас не

Цитата

вернет нас в цикл

, а выведет из метода... этого не надо.

Nestor

Дата 20.2.2008, 15:33 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(Alenka_ @ 20.2.2008, 01:19

)

ну вот, охарактеризовали...

Я имел в виду не человека, а подобие переводчика Promt, только осуществляющего перевод из одного языка программирования в другой. Во всяком случае, обидеть не хотел.

Цитата(Alenka_ @ 20.2.2008, 01:19

)

А вот return нас не
Цитата

вернет нас в цикл
, а выведет из метода... этого не надо.

Alenka_

Дата 20.2.2008, 23:06 (ссылка)

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

Загрузка ...

Шустрый

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

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

Nestor, Я и не думала обижаться... smile

это я шучу так...

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