Занятие 3

Генерация всех перестановок

Требуется сгенерировать все перестановки чисел 1, …, `n`

int n;
int b[100]; // массив с числами 1,..., n
void rec(int i)
{ int j, t;
  if(i==n)
  { for(i=0; i<n; ++i)
      printf("%d%c",b[i],i<n-1?' ':'\n');
    return;
  }
  // подстановка на i-ое место всех элементов с i по n-1
  for(j=i; j<n; ++j)
  { 
    t=b[i];
    b[i]=b[j];
    b[j]=t;
    rec(i+1);
  }
  // восстановление состояния массива
  t=b[i];
  for(j=i+1; j<n; ++j)
    b[j-1]=b[j];
  b[n-1]=t;
}

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

Если в массиве b могут встречатся повторяющиеся значения, то нужно немного исправить программу:

int n;
int b[100]; // массив с числами 1,..., n
void rec(int i)
{ int j, t;
  if(i==n)
  { for(i=0; i<n; ++i)
      printf("%d%c",b[i],i<n-1?' ':'\n');
    return;
  }
  // подстановка на i-ое место всех элементов с i по n-1
  for(j=i; j<n; ++j)
  { if(i!=j && b[i]==b[j]) // пропускаем совпадающие элементы
      continue;
    t=b[i];
    b[i]=b[j];
    b[j]=t;
    rec(i+1);
  }
  // восстановление состояния массива
  t=b[i];
  for(j=i+1; j<n; ++j)
    b[j-1]=b[j];
  b[n-1]=t;
}