рекурсия - печать uniq подгрупп

Question

мой код:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>


void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {

        printf(" %d ", arr[i]);
    }
    printf("\n");

}

void tr8Helper(int* arr, int n, int index, int b, int* used)
{
    if (index == n )
    {

        printArr(arr, n);

    }
    else {

        for (int i = 0; i < b; i++) {

            arr[index] = i;
            tr8Helper(arr, n, index + 1, b, used);
        }


    }

}


void tr8(int num, int b)
{
    int* myArray = (int*)malloc(num * sizeof(int));
    int* used = (int*)malloc(b * sizeof(int));
    tr8Helper(myArray, num, 0, b, used);
}

int main() {
    tr8(3, 3);
}

это мой код до сих пор, и это то, что моя рекурсия печатает для b = 2, n = 3: вывод для этого кода вещьУ меня проблемы с тем, как использовать «используемый» массив, чтобы выходные данные были, например, b = 3 n = 3 запрошенный выходной сигнал Мне трудно думать об этомпроблема, как об этом подумать сверху. Как сказать, я использовал этот номер, не используйте его снова. или, может быть, пропустить этот ряд, когда печать происходит. Пожалуйста, поделитесь со мной своими мыслями и идеями и, возможно, некоторыми советами о том, как справиться с такими вопросами

Answer 1

Судя по вашим данным и ожидаемым результатам, я думаю, что когда вы говорите «уникальные подгруппы», вы имеете в виду k -перестановки . Если это так, то вам просто нужно использовать массив used (который в вашем коде передается, но фактически не используется). Я добавил три новые строки в tr8Helper;больше ничего не нужно менять.

void tr8Helper(int* arr, int n, int index, int b, int* used) {
  if (index == n) {
    printArr(arr, n);
  } else {
    for (int i = 0; i < b; i++) {
      if (!used[i]) {     // (1) do not use i unless it is available
        used[i] = 1;      // (2) mark i as used so we don't use it twice
        arr[index] = i;
        tr8Helper(arr, n, index + 1, b, used);
        used[i] = 0;      // (3) mark i as available so future k-perms can use it
      }
    }
  }
}