VPF::Перебор комбинаций - Форум программистов

distorti

Дата 7.10.2006, 04:47 (ссылка)

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

Загрузка ...

Новичок

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

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

Привет всем!

Такая задача:
самым эффективным способом сгенерировать всевозможные комбинации из элементов массива.
например:

input:
[1,3,5]

output:
[1,3,5]
[1,5,3]
[3,1,5]
[3,5,1]
[5,1,3]
[5,3,1]

MBo

Дата 7.10.2006, 09:54 (ссылка)

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

Загрузка ...

Бывалый

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

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

Это называется перестановки (permutation)
Думаю, теперь найти труда не составит

Kuvaldis

Дата 7.10.2006, 10:09 (ссылка)

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

Загрузка ...

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

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

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

distorti,
Если у тебя не могут быть повторяющиеся элементы в массиве, то можно сделать рекурсивно, "по индукции": на каждой итерации цикла ставим на место первого элемента очередной элемент строки длины n и для остальных элементов справа генеририуем перестановки (n - 1) порядка.

Думаю, будет не сложно преобразовать программу для работы с целочисленными массивами. smile

Код


//---------------------------------------------------------------------------
// вход: х -  получаемая перестановка. str - указатель на элемент в исходной строке
// (будет двигаться), n - текущая длина исходной перестановки
int perestanovka (char* x, char* str, int n)
{
  char  t;
  int   j, i;
  static int count = 1;
  static long size = fact(n);
  char* buf;

  if (n == 2)
  {
      printf("%-3d", count++);
      Output(x);
      obmen (str, str + 1);
      printf("%-3d", count++);
      if (count >= size) // сброс для нового запуска программы с новыми данными
         count = 1;
      Output(x);
  }    
  else
  {
     if (!(buf = (char*) malloc((n + 1) * sizeof(char))))
     {
        puts("no memory");
        getch();
        return 1;
     }
     for (i = 0; i < n; i ++)
     {
        strcpy(buf, str);
        t = str[i];       // меняем местами 0 и i элементы
        str[i] = str[0];
        str[0] = t;
        if (perestanovka (x, str + 1, n - 1)) return 1;
        t = str[i];       // восстановление: меняем местами 0 и i элементы
        str[i] = str [0];
        str[0] = t;
        strcpy(str, buf);
     }
     free(buf);
  }

   return 0;
}
//---------------------------------------------------------------------------
void obmen (char* s1, char* s2)
{
 char t;

  t = *s1;
  *s1 = *s2;
  *s2 = t;
  return;
}
//---------------------------------------------------------------------------
void Output (char* str)
{
    int i = 0;

    putchar('\t');
    while (str[i])
    {
       putchar(str[i]);
       putchar('\t');
       i++;
    }
    puts ("");
    return;
}
//---------------------------------------------------------------------------
long int fact(int n)
{
     if ((n == 1) || (n == 0))
       return 1;
     else
       return (n * fact(n - 1));

}
//---------------------------------------------------------------------------

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

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

distorti

Дата 8.10.2006, 13:55 (ссылка)

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

Загрузка ...

Новичок

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

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

Spasibo, ideja jasna

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