Xpoint
   [напомнить пароль]

Все перестановки массива

Метки: [без меток]
2004-11-25 18:22:29 [обр] Владимир Решетников(0/2)[досье]
Сразу хочу пояснить, что мой вопрос не о том, как получить все перестановки массива. Задача в следующем. Будем говорить об отрезке натурального ряда [1..N]. Допустим, мы каким-либо образом упорядочили все N! перестановок этого ряда (не важно, каким именно). Сделаем этот порядок циклическим, положив, что сразу за последней перестановкой следует первая. Требуется написать функцию, которая, получив в качестве аргумента любую из перестановок этого отрезка, выдаст в качестве результата следующую перестановку (в смысле выбранного нами порядка). Другими словами, функция должна быть такой, чтобы подавая ей на вход ее же результат из предыдущей итерации, я мог бы за N! итераций получить все N! перестановок в некотором (повторюсь, не важно в каком) порядке.
Заранее благодарен за помощь.
спустя 20 минут [обр] Закиров Руслан(0/343)[досье]

Программа на С которая перебирает все неповторяющиеся перестановки символов в строке.
Символы вначале должны быть отсортированы слево на право по увеличению. То есть если у вас строка состоит из букв аглийского алфавита, то первая последовательность a..z, а последняя z..a. Самое главное алгоритм пропускает одинаковые варианты.

#include <stdio.h>
#include <string.h>
                                                                                                                                                                      
int main()
{
        char str[20];
        int n,k,t,y;
        int ttt=1;
        strcpy(str,"111223");
        printf ("%s\n",str);
        n=strlen(str)-1;
while(1)
{
        k=n-1;
        while ((str[k]>=str[k+1])&&(k>=0)) k--;
        if (k<0) {return(0);}
        t=k+1;
        while ((t<n)&&(str[t+1]>str[k])) t++;
        y=str[k];
        str[k]=str[t];
        str[t]=y;
        t=0;
        while (t<(int)((double)(n-k)/2.0))
        {
                y=str[n-t];
                str[n-t]=str[k+1+t];
                str[k+1+t]=y;
                t++;
        }
        printf ("%s\n",str);
}
}

За код не ругать писал, много веков назад :) только в качестве эксперимента

спустя 7 минут [обр] Алексей В. Иванов(3/2861)[досье]
Владимир Решетников[досье] То ли я ничего не понял, то это слишком просто. Пример можете привести? Т.е. пример вызовов от аргументов и возвраты
спустя 11 минут [обр] Владимир Решетников(0/2)[досье]
Закиров Руслан[досье]
Опасался получить ответы такого рода и старался объяснить это в шапке темы. Но, видимо у меня трудности с ясным выражением мыслей :(
Я знаю, как получить все перестановки массива. Алгоритм, который интересует меня, действительно должен пропускать одинаковые варианты, иначе он не смог бы за N! итераций выдать все N! перестановок.
Но мне нужно создать функцию, которая по данной перестановке находила бы следующую в смысле некоторого выбранного порядка. Конечно, можно представить себе такое решение, которое на каждой итерации строило бы (каждый раз одним и тем же способом) список всех возможных перестановок, находило среди них данную и выдавало бы в качестве ответа следующую из списка. Но так на каждую итерацию будет выполняться O(N!) действий. Меня интересует гораздо более эффективное решение. Интуиция мне подсказывает, что оно существует, но пока мне не удалось его построить.
спустя 52 минуты [обр] Алексей В. Иванов(3/2861)[досье]
Но, видимо у меня трудности с ясным выражением мыслей :(

Может.

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

Хотя возможно, что я уже не владею ясным мозгом.

спустя 1 час 57 минут [обр] Maestro(0/9)[досье]
Кажется понял, поэтому уточняю:
необходима функция f(int *arr), которая после каждой итерации изменит массив так, что в следующий раз он будет таким же только через N! - 1 последовательных вызовов.
При этом проблема состоит не в том, чтобы просто перебрать все подстановки, а найти следующую за данной, что несколько сложнее, так как не всегда очевидно, в какую сторону должна "измениться" подстановка в данный момент времени.
Я бы сказал, что нужно найти некоторую меру на множестве всевозможных подстановок, после чего увеличивать ее на каждом шаге. Так как у нас используются только числа от 1 до N, то вполне логично использовать, например, использовать полином с основанием N+1 для подсчета меры. (пока это только идея, на написание кода нет времени, может ближе к утру :0)
спустя 10 часов [обр] Алексей Полушин(0/231)[досье]
void swap(int *a,int *b) {
  int c;
  c=*a; *a=*b; *b=c;
}

int cmp(const void *a,const void *b) {
 return *(int *)a-*(int *)b;
}

void sort(int *a,int n) {
  qsort(a,n,sizeof(int),cmp);
}

void nextp(int *a,int n) {
  int i,j;
  if (n<=1) return;
  if (n==2) {
    swap(&a[0],&a[1]);
    return;
  }
  if (a[n-1]>a[n-2]) {
    swap(&a[n-1],&a[n-2]);
    return;
  }
  for (i=n-2;i>0;--i) {
    if (a[i]>a[i-1]) {
      for (j=n-1;j>i;--j)
        if (a[j]>a[i-1]) break;
      swap(&a[i-1],&a[j]);
      sort(&a[i],n-i);
      return;
    }
  }
  sort(&a[0],n);
}
спустя 34 минуты [обр] Алексей Полушин(0/231)[досье]

Подумав, можно немного упростить код

void nextp(int *a,unsigned n) {
  int i,j;
  for (i=n-1;i>0;--i)
    if (a[i]>a[i-1]) {
      for (j=n-1;j>i;--j)
        if (a[j]>a[i-1]) break;
      swap(&a[i-1],&a[j]);
      break;
    }
  sort(&a[i],n-i);
}

(функции sort и swap смотрите выше)
код работает с массивом с неповторяющимися элементами
находит следующию перестановку в "натуральном" порядке, и переводит "максимальную" перестановку в "минимальную"

спустя 11 минут [обр] Алексей Полушин(0/231)[досье]

Подумав еще немного, код можно оптимизировать, отказавшись от функции sort (и ускорив выполнение)

void nextp(int *a,unsigned n) {
  int i,j;
  for (i=n-1;i>0;--i)
    if (a[i]>a[i-1]) {
      for (j=n-1;j>i;--j)
        if (a[j]>a[i-1]) break;
      swap(&a[i-1],&a[j]);
      break;
    }
  for(j=n-1;j>i;--j,++i)
    swap(&a[i],&a[j]);
}

(надеюсь, что это мой окончательный вариант)

спустя 37 минут [обр] Алексей Полушин(0/231)[досье]
Подумал еще, и понял, что даже если в массиве есть повторяющиеся значения, этот код тоже работает правильно.
спустя 3 часа 31 минуту [обр] Владимир Решетников(0/2)[досье]

Maestro[досье]

необходима функция f(int *arr), которая после каждой итерации изменит массив так, что в следующий раз он будет таким же только через N! - 1 последовательных вызовов.

Абсолютно верно. А то я уже стал бояться, что мою мысль так никто и не поймет.
Алексей Полушин[досье]
Большое спасибо! Именно это я и искал. Но не совсем понял, какой смысл Вы вкладываете в понятия "максимальная" и "минимальная" перестановка.
Как я понял, это решение с трудоемкостью O(N^2) на итерацию. Интересно, возможно ли O(N*Log(N)) ?
Алексей В. Иванов[досье]

  1. Многие пользователи забывают сказать зачем им это нужно...
  2. Зря грузите пустой теорией...

Спасибо за дельные советы. Обязательно учту.
Если кому интересно, эта задача возникла у меня в связи с необходимостью перевести формальный язык запросов системы NBU R-Bank в регулярные выражения. Но, IMHO, детальное описание прблемы было бы в данном случае менее эффективным, чем сделанная мной попытка формального описания алгоритма.
С уважением, Владимир.

спустя 1 час 10 минут [обр] Закиров Руслан(0/343)[досье]
Мой код делает тоже самое. Я прекрасно понял, что вам нужно. Жаль что вы не стали рабираться сами, а попросили готовое решение.
спустя 2 часа 43 минуты [обр] Владимир Решетников(0/2)[досье]

Закиров Руслан[досье]
Прошу прощения, если я Вас не понял и не смог сразу по достоинству оценить Ваш ответ. Но признаюсь, что до сих пор, вглядываясь в Ваш код, я не могу увидеть функцию, которая, согласно блестящему определению господина Maestro

после каждой итерации изменит массив так, что в следующий раз он будет таким же только через N! - 1 последовательных вызовов.

Возможно тело цикла while можно переделать под функцию... Впрочем, это ведь писано много веков назад :) Не сомневаюсь, что код, который Вы пишете сейчас, легко воспринимается без комментариев.
Но, в любом случае, это мой промах.

спустя 4 часа 23 минуты [обр] Алексей Полушин(0/231)[досье]
Но не совсем понял, какой смысл Вы вкладываете в понятия "максимальная" и "минимальная" перестановка.

Ну вы же в начале говорили про первую и последнюю перестановки.
Я имел ввиду "натуральную" сортировку - больше тот из двух массивов, в котором первый несовпадающий элемент больше.
К примеру, в этом смысле (1,2,3,4) - "минимальная", а (4,3,2,1) - "максимальная" перестановка первых четырех натуральных чисел.

Как я понял, это решение с трудоемкостью O(N^2) на итерацию.

Нет, таки O(N)
Это только кажется, что там вложеный цикл. :)

спустя 37 минут [обр] Maestro(0/9)[досье]

Что-то вчера совсем замотался, но и сегодня никто ничего не выложил, поэтому вот мой код (выкладываю полностью всю программу):

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

void swap_elements(int m[], int i, int j)
{
   int c = m[i];
   m[i] = m[j];
   m[j] = c;
}

void swap_subarray(int m[], int i, int j)
{
// необходимо поменять "развернуть" кусок массива m, включающий индексы [i, j]
// не будем заводить новых переменных - попортим старые (уже неважно, даже если они ссылки)
   while (i < j)
      swap_elements(m, i++, j--);
}

int find_min_but_greater(int m[], int i, int N)
{
//   среди элементов хвоста массива m ищем минимальный элемент, больший чем m[i-1]
   int j_min = i;
   for (int j = i + 1; j < N; j++)
   {
      if ((m[j] > m[i - 1]) && (m[j] < m[j_min]))
         j_min = j;
   }
   return j_min;
}

void next(int m[], int N)
{
   int i = N - 1;
   while (i > 0)
   {
      if (m[i - 1] < m[i])
      {
// нашли место, вида ????? m[i-1] < m[i] > m[i+1] > ... > m[N - 1]
// сейчас надо найти номер j > i, который минимальным образом превосходит m[i - 1]
         int j_min = find_min_but_greater(m, i, N);
// теперь обменяем элементы массива с индексами j_min и i - 1
         swap_elements(m, j_min, i - 1);
// теперь осталось только перевернуть часть массива с индексами [i, N - 1]
         swap_subarray(m, i, N - 1);
// очередной шаг сделан - можно возвращаться
         return;
      }
// обязательно двигаемся
      i--;
   }
// у нас массив оказался упорядоченным по убыванию, значит необходимо упорядочить по возрастанию
// мог бы написать, например, for (i = 0; i < N; i++) m[i] = i + 1;
// где "+ 1" используется для создания массива 1..N вместо 0..N-1
// но воспользуемся уже готовой функцией, которая корректно работает с любыми массивами
   swap_subarray(m, 0, N - 1);
}

int main(int argc, char *argv[])
{
   int i;
   int N = 4;

   if (argc > 1)
      N = atoi(argv[1]);
   printf("N = %d\r\n", N);
   
   int *m = new int[N];
// инициализация массива
   for (i = 0; i < N; i++)
      m[i] = i + 1;

// вычислим количество итераций
   int factor = 1;
   for (i = 1; i <= N; i++)
      factor *= i;

   while (factor >= 0)
   {
      printf("step %4d: ", factor);
// напечатаем массив на очередном шаге
      for (i = 0; i < N; i++)
      {
         printf("%2d ", m[i]);
      }
      printf("\r\n");
      factor--;
// и сделаем этот шаг
      next(m, N);
   }

   delete m;
   return 0;
}

Хочу сделать пару замечаний к тексту (надеюсь смысл работы программы будет понятен из комментариев):

  1. Искомая функция называется next. Ей в качестве параметров передается массив и его длина. Использует мою предыдущую идею по упорядочиванию. Хотя эта функция и использует три вспомогательные, но последние можно без проблем вставить на соответствующие места и все продолжит работать.
  2. Функция корректно работает с любым массивом из N чисел, в котором нет повторяющихся элементов. То есть, например, для массива [1, 5, 65, 231, 642, 832] она также получит коррекнтые перестановки.

Если есть вопросы - спрашивайте.

спустя 9 минут [обр] Maestro(0/9)[досье]
Кстати, если использовать функцию с памятью (то есть сохраняющую небольшой объем информации между вызовами), или перебор всех перестановок в цикле (фактически предыдущий вариант), то можно выводить такую последовательность, в которой каждые две подряд идущие перестановки будут отличаться только перестановкой двух соседних элементов. То есть последовательные пары имеют вид AAAAAxyBBBBB и AAAAAyxBBBBB (местами поменялись только отдельные элементы x и y).
спустя 2 дня 21 час [обр] Владимир Решетников(0/2)[досье]

Maestro[досье]
Если я правильно Вас понял, можно написать функцию, которой достаточно передать в качестве аргументов две последние перестановки массива и

которая после каждой итерации изменит массив так, что в следующий раз он будет таким же только через N! - 1 последовательных вызовов

причем два последовательных результата будут отличаться только значениями элементов на двух (соседних?) позициях.
Или невозможно обеспечить условие соседних?

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

спустя 3 часа 37 минут [обр] Maestro(0/9)[досье]

Владимир Решетников[досье]
Во-первых, в моем "определение", касаемое функции "которая после каждой итерации изменит массив так, что в следующий раз он будет таким же только через N! - 1 последовательных вызовов" не хватает замечания по поводу того, что получившийся массив будет состоять из тех же элементов, что и исходный, причем элементы исходного должны быть попарно различны.

Если я правильно Вас понял, можно написать функцию, которой достаточно передать в качестве аргументов две последние перестановки массива и причем два последовательных результата будут отличаться только значениями элементов на двух (соседних?) позициях.
Или невозможно обеспечить условие соседних?

Да, писал именно про соседние элементы. Но двух последних перестановок может не хватить. Точнее, я представляю как решить подобную задачу, но с использованием внутренней (или передаваемой) памяти, размер которой на порядок меньше размера памяти, занимаемой массивом. Однако эту память заполнять будет сама функция.

Powered by POEM™ Engine Copyright © 2002-2005