Создание всех подмножеств рекурсивно без использования массива - PullRequest
Новая
       31

Создание всех подмножеств рекурсивно без использования массива

0 голосов
/ 28 октября 2018

Мы получаем неотрицательное целое число n от пользователя, и мы должны напечатать все подмножества набора ({1,2,3,...,n}).(n<=20)

, например, для n=3 мы должны напечатать: 

{1 , 2 , 3}
{1 , 2}
{1 , 3}
{1}
{2 , 3}
{2}
{3}
{}

, s необязательно, и последовательность может быть напечатана без запятой.(как {1 2 3}) Я должен добавить, что последовательность подмножеств должна быть точно такой же, как в примере.Имеется в виду сначала подмножества, которые имеют 1, затем подмножества, которые имеют 2 и .... Самое длинное подмножество должно быть напечатано первым.(лексикографический от самого большого подмножества (самого набора) к нулевому набору)

Я вижу много кодов в Интернете, которые решают эту проблему с массивами или используют битовый массив, который указывает, используем ли мы число или нет,Проблема заключается в том, что в этом вопросе нам не разрешено использовать массив любого типа или другие структуры данных, такие как вектор и т. Д.Даже использование поведения массива чего-то вроде строки полностью запрещеноЭто должно быть решено только с помощью рекурсии.

Нам также не разрешено использовать какие-либо расширенные функции.Например, если мы напишем его с помощью C, нам разрешено просто использовать stdio.h или для C++, разрешено только <iostream> и никакой другой библиотеки.

Я не знаю, каксделать это без каких-либо массивов.Как проверить, какой номер он должен распечатать и в то же время управлять {}.

PS1.Вопрос заключается в простом поколении powerset с этими условиями:

ИСПОЛЬЗОВАНИЕ Массива, STRING и ДАЖЕ ЦИКЛОВ ПОЛНОСТЬЮ ЗАПРЕЩЕНЫ.ПРОСТО РЕКУРСИЯ.

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

PS2.

Я пишу этот код с помощью Джорджа, но он не работает нормально,Он не имеет ничего похожего на 1 2 4. Он также повторяет некоторые случаи. 

#include <stdio.h>


void printAllSets (int size)
  {printRows (size, 1);}

void printRows (int size , int start)
{
  if (start<=size)
  {printf( "{ ");
  printRow (start, size);
  printf ("}");
  printf ("\n");}
  if (start <= size)
  {printRows(size -1 , start);
    printRows (size , (start + 1));}
}
printRow (int start, int limit)
{

  if (start <= limit)
  {

    printf ("%d ",start);
    printRow (start +1, limit);
  }
}


int main()
{
    printAllSets(5);
    printf("{ }");
    return 0;
}

PS3.

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

Ответы [ 4 ]

0 голосов
/ 12 ноября 2018

По определению, powerset набора k, powerset k, является набором всех возможных наборов, содержащих элементы из этого данного набора, включая сам пустой набор.Ясно, что когда k - это пустой набор, powerset [] - это просто набор, содержащий пустой набор, [ [] ].Теперь, учитывая набор мощности k, powerset k, блок питания для k плюс дополнительный элемент E, powerset (K+E), будет включать все возможные наборы, содержащие элементы без E, powerset k,плюс те же самые элементы, за исключением того, что теперь все содержат E

псевдокод ... 

let powerset k =
   match k with
   | [] -> [[]]
   | x:xs -> x * powerset xs + powerset xs

или с эквивалентной производительностью хвостового вызова 

let powerset k =
   let (*) e ess = map (es -> e::es) ess
   reduce (e ess -> (e * ess) ++ ess) [ [] ] (reverse k)

....(В F #) 

let rec powerset k =
  match k with
  | []    -> [ [] ]
  | x::xs -> 
      let withoutE = powerset xs
      let withE = List.map (fun es -> x::es) withoutE
      List.append withE withoutE

или более кратко 

let rec powerset = function
  | []    -> [ [] ]
  | x::xs -> List.append (List.map (fun es -> x::es) (powerset xs)) (powerset xs)

Лучшая версия позволит оптимизировать хвостовой вызов ... что мы достигли с помощью общих функциональных шаблонов: 

let rec powerset2 k = 
  let inline (++) a b = List.concat [a;b]
  let inline (+*) a bs = List.map (fun b -> a::b) bs
  List.fold 
    (fun ac a -> (a +* ac) ++ ac)
    [ [] ] 
    (List.rev k)

- все это заняло у меня некоторое время, чтобы открыть заново.Это была забавная маленькая головоломка.:)

0 голосов
/ 29 октября 2018

Рекурсивные алгоритмы очень интенсивно используют память.Здесь алгоритм для n <= 31

#include <iostream>

void bin(unsigned bit, unsigned k, unsigned max_bits) {
    if (bit == max_bits) {
        std::cout << "{";
        bin(bit - 1, k, max_bits);
    }
    else {
        if ((k & (1u << bit)) != 0) {
            std::cout << (max_bits - bit) << " ";
        }
        if (bit != 0) {
            bin(bit - 1, k, max_bits);
        }
        else {
            std::cout << "}" << std::endl;
        }
    }
}

void print(unsigned k, unsigned n, unsigned max_bits) {
    bin(max_bits, k, max_bits);
    if (k != 0) {
        print(k - 1, n, max_bits);
    }
}

int main()
{
    unsigned n;
    std::cin >> n;
    print((1u << n) - 1u, 1u<<n, n);
    return 0;
}

Первая рекурсия print перечисляет k от 2^n-1 до 0, вторая рекурсия bin перечисляет все биты k и выводит ненулевое значениебиты.Например, max_bits = 5 и k = 19 равны 10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0, биты 4,1,0 взаимодействуют, как установлено {5-4,5-1,5-0} => {1,4,5}

0 голосов
/ 30 октября 2018

Я думаю, что мы можем решить это итеративно, что, как мы можем предположить, также может быть преобразовано в рекурсию, хотя это кажется ненужным.Учтите, что мы можем отменить любую комбинацию по заданному индексу, используя общеизвестные знания.Поэтому все, что нам нужно сделать, - это подсчитать, сколько ранних комбинаций мы пропускаем, и сколько нам нужно разблокировать на каждом этапе итерации (возможно, я что-то упустил в следующем, но я думаю, что общая идея обоснована): 

Skip 0, unrank from `3 choose 3`
`2 choose 2` combinations
{1 , 2 , 3} 

Skip 0, unrank from `3 choose 2`
`2 choose 1` combinations
{1 , 2}
{1 , 3}

Skip 0, unrank from `3 choose 1`
`2 choose 0` combinations
{1}

Skip `3 choose 2 - 2 choose 2`,
unrank from `3 choose 2`
`1 choose 1` combinations
{2 , 3}

Skip `3 choose 1 - 2 choose 1`,
unrank from `3 choose 1`
`1 choose 0` combinations
{2}

Skip `3 choose 1 - 1 choose 1`,
unrank from `3 choose 1`
`0 choose 0` combinations
{3}

Empty set
{}
0 голосов
/ 28 октября 2018

Альтернативой циклам является рекурсия.

Чтобы решить эту проблему (я думаю ... не проверял ее), я исследую эту проблему путем табулирования даты выборки и различения трех состояний: Size, Start и Limit спрогрессия выглядит следующим образом: 

Size  Start Limit   Output
  10      1    10    1..10
  10      1     9     1..9
              ...      ...
  10      1     1        1
  10      2    10    2..10
  10      2     9     2..9
              ...      ...
  10      2     2        2
        ...   ...      ...
  10     10    10       10

Следующий рекурсивный алгоритм в псевдокоде может помочь: 

printAllSets size
  printRows size 1

printRows size start
  print "{"
  printRow start size
  print "}"
  print CRLF
  if start <= size
    printRows size (start + 1)

printRow start limit
  if start <= limit
    print start + SPACE
    printRow start (limit - 1)

Надеюсь, это по крайней мере поможет вам направить вас в правильном направлении.

...