Перестановка для чисел в C - PullRequest
Новая
       22

Перестановка для чисел в C

1 голос
/ 22 сентября 2010

Я пытаюсь написать функцию C для перечисления всех перестановок набора чисел, в группах по пять, включая повторяющиеся числа: 

15-11-49-43-5
2-30-34-6-11

Так что достаточно легко написать функцию для захватавсе перестановки набора чисел и выбрасывают их, но сопоставлены с определенным размером группы, я несколько застрял ..

Ответы [ 5 ]

1 голос
/ 22 сентября 2010

Хотите ли вы получить конкретную перестановку, например,

  • перестановка 1 == 1, 1, 1, 1, 1
  • перестановка 2 == 1, 1, 1, 1, 2
  • перестановка 49 == 1, 1, 1, 1, 49
  • перестановка 50 == 1, 1, 1, 2, 1
  • перестановка 42000000 == 8, 14, 49, 35, 42

Преобразуйте желаемое число (минус 1) в основание 49 и используйте «цифры» (плюс 1) для результата. 

42000000 - 1 = 41999999
41999999 = (7 * 49^4) + (13 * 49^3) + (48 * 49^2) + (34 * 49) + 41
result      8            14            49            35         42
1 голос
/ 22 сентября 2010 
void visit(int *Value, int N, int k)
{
  static level = -1;
  level = level+1; Value[k] = level;

  if (level == N)
    print(Value, N);
  else
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)
        visit(Value, N, i);

  level = level-1; Value[k] = 0;
}

Для получения дополнительной информации вы можете посетить http://www.bearcave.com/random_hacks/permute.html

0 голосов
/ 22 сентября 2010

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

Вы просто ищете простой счет: 

for (a[0] = 1; a[0] <= 49; a[0]++)
  for (a[1] = 1; a[1] <= 49; a[1]++)
    for (a[2] = 1; a[2] <= 49; a[2]++)
      for (a[3] = 1; a[3] <= 49; a[3]++)
        for (a[4] = 1; a[4] <= 49; a[4]++)
          printf("%d-%d-%d-%d-%d\n", a[0], a[1], a[2], a[3], a[4]);
0 голосов
/ 22 сентября 2010

Если вы знаете, как найти все перестановки, но не все комбинации размера 5, просто найдите все перестановки:

int A [49] = {0, 0, ..., 0, 1, 1, 1, 1, 1};

Каждая перестановка массива A соответствует комбинации, содержащей число (i + 1), если и только если A [i] == 1, для каждого i в [0, 49).

0 голосов
/ 22 сентября 2010

Я бы разделил это на две задачи: а) найти все комбинации nCk вашего массива размера n b) найти все перестановки массива длины k. Вы сказали, что уже знаете, как выполнять перестановки, поэтому давайте сосредоточимся на комбинациях: 

void combinations(int *arr, int *comb, int n, int k, int kCurr)
{
    if(kCurr >= k)
    {
        permutations(comb, k);
        return;
    }
    int i;
    for(i=0; i<n; ++i)
    {
        comb[kCurr] = arr[i];
        combinations(arr+i, comb, n-i, k, kCurr+1);
    }
}

который будет называться так: 

int myArray[49] = {1, 2, ..., 49};
int myCombs[5];
combinations(myArray, myCombs, 49, 5, 0);

Это вычисляет все комбинации 49C5 путем построения массива myCombs, а когда он полон, вызывает функцию permutations. Если permutations реализован правильно, вы распечатаете все перестановки всех комбинаций 49C5.

РЕДАКТИРОВАТЬ: Duh, вы можете просто сделать combinations(arr, comb, n, k kCurr+1) в качестве рекурсивного шага, а затем просто распечатать массив в базовом случае (или сделать что-нибудь).

...