VPF::[C++] Найти подмножества множества m

mus

Дата 25.5.2005, 20:09 (ссылка)

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

Загрузка ...

Шустрый

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

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

Стоит задача написать программу на Borland C 3.01 которая находит и выводит на экран все подмножества множества n заданной длины.
пример:

Код


m = {1,2,3};
len_of_n = 2; // длина подмножества

=================
на выходе:
1,2
1,3
2,3

Буду премного благодарен!
Комбинаторика интересная вещь, но найти мало мальски хорошего примера на C я не смог.

Это сообщение отредактировал(а) mus - 25.5.2005, 20:12

gepard

Дата 26.5.2005, 03:16 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата

на выходе:
1,2
1,3
2,3

А разве не:
1,2
2,1
1,3
3,1
2,3
3,2
smile

Если нет, то вот:

Код


#include <stdio.h>

void ,ain()
{
    unsigned int mass[5] = {66, 83, 99, 277, 22};
    unsigned int tempId = 0;

    while((tempId != 4))
    {
        for (int i = tempId; i < 5; i++)
            printf("%d %d", mass[tempId], mass[i]);

        tempId++;
    }
}

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

Когда начинаются цифровые войны, а траффик разносит моё сознание по бесконечным просторам инета, подобно ветру, разносящему листву по полям, тогда и только тогда я чувствую себя свободным!
© Я, Берсерк, что значит - Неистовый.

mus

Дата 26.5.2005, 10:01 (ссылка)

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

Загрузка ...

Шустрый

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

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

gepard
Спасибо за пример. Сейчас попробую реализовать.
Возможно - Ваш вариант, когда я получал лаб. работу, не уточнил.
Если Вам не сложно, будьте любезны, дайте на всякий пожарный код с Вашим примером (где возможно перепостроения одинаковых элементов).
Заранее благодарю!

mus

Дата 26.5.2005, 10:40 (ссылка)

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

Загрузка ...

Шустрый

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

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

Не нужно Вашего варианта. Я сейчас прочел код и понял как это сделать. Элементарно. На будущее для тех, кто не понял, в цикле поменяйте for(i = TempId;... на for(i =0;...

segmentation_fault

Дата 26.5.2005, 20:07 (ссылка)

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

Загрузка ...

Шустрый

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

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

Может быть я недопонял задание но код gepardа будет работать только с длиной поднможества = 2. Или в задании указано что подмножества не могут быть длиннее чем 2?

Это сообщение отредактировал(а) segmentation_fault - 26.5.2005, 20:08

gepard

Дата 27.5.2005, 06:57 (ссылка)

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

Загрузка ...

Эксперт

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

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

Только с 2 в моём примере.

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

Heo

Дата 21.12.2006, 12:25 (ссылка)

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

Загрузка ...

Новичок

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

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

gepard, не могли бы вы выложить код, который бы выводил из 1,2,3 числа все комбинации (1 2 3 12 13 21 23 и тд)

Rockie

Дата 21.12.2006, 14:10 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

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

Цитата(mus @ 25.5.2005, 20:09

)

все подмножества множества n заданной длины.

mus, imho во множестве (как и в подмножестве) порядок не имеет значения, то есть {1,2} равносильно {2,1}

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

Чтобы иметь большой гардероб - надо иметь большой гардероб.

Kuvaldis

Дата 21.12.2006, 20:03 (ссылка)

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

Загрузка ...

механик-вредитель

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

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

mus,

Цитата

Элементарно. На будущее для тех, кто не понял, в цикле поменяйте for(i = TempId;... на for(i =0;...

Так делать нельзя, так как

Цитата

во множестве (как и в подмножестве) порядок не имеет значения, то есть {1,2} равносильно {2,1}

Соответственно, нужно ввести отношение порядка какое-нибудь, чтобы данная ситуация однозначно разруливалась, Например, числа подмножества выводятся по возрастанию. Что равносильно
for (int i = tempId; i < 5; i++)

Heo,
Смотри бинарные коды Грея, на форуме уже я отвечал на этот вопрос (там, правда, Паскаль, но идея будет и так ясна)

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

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Carlos0N

Дата 12.2.2011, 02:00 (ссылка)

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

Загрузка ...

Шустрый

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

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

Ребят, возникла задача написать функцию, на вход к которой идёт размерность подмножеств, которые надо найти в массиве, на выход соответственно сами эти подмножества.
Я чёт туплю и не могу сообразить как это сделать))
Насчет кода Грея, я в коде на паскале не разбираюсь, синтаксис не понятен достаточно сильно, если не трудно, расскажите как это сделать.
Можно даже вариант с повторяющимися подмножествами типа (1,2) и (2,1), я их потом удалю, но лучше без них конечно, т.к. при больших размерах их будет через чур много.

Это сообщение отредактировал(а) Carlos0N - 12.2.2011, 02:03

Carlos0N

Дата 12.2.2011, 02:25 (ссылка)

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

Загрузка ...

Шустрый

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

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

Код


foo()
{
  if test $2 -eq 1; then
    seq 1 $1
  else
    seq $2 $1 \
      | while read i; do
          foo $(($i - 1)) $(($2 - 1)) | sed 's/$/ '$i'/'
        done
  fi
}

$ foo 6 3
1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5
1 2 6
1 3 6
2 3 6
1 4 6
2 4 6
3 4 6
1 5 6
2 5 6
3 5 6
4 5 6

кто нибудь может переписать этот пример на псевдокод хотя бы?)

Это сообщение отредактировал(а) Carlos0N - 12.2.2011, 02:26

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