Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] Найти подмножества множества m

Автор: mus 25.5.2005, 20:09

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

Код


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

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

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

Автор: gepard 26.5.2005, 03:16

Цитата

на выходе:
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

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

Автор: mus 26.5.2005, 10:40

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

Автор: segmentation_fault 26.5.2005, 20:07

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

Автор: gepard 27.5.2005, 06:57

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

Автор: Heo 21.12.2006, 12:25

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

Автор: Rockie 21.12.2006, 14:10

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

)

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

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

Автор: Kuvaldis 21.12.2006, 20:03

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

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

Автор: Carlos0N 12.2.2011, 02:25

Код


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

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