Как можно порождать перестановки с дополнительными ограничениями для элементов итеративно?

Question

[readical]

Существуют ли примеры кода или алгоритмы, которые могут порождать перестановки с дополнительными ограничениями для элементов итеративно?
То есть для каждых двух элементов должно быть истинно определенное арифметико-логическое выражение.
То, что я находил в старых книгах, использует goto.
Рекурсивно задачи решаются легко.

Comments

[bobrovskyserg]

Существуют.
Но отвечать тебе не хочется - судя по профилю, тебе плевать на ответы.

Answer 1

[Mrrl]

А чем не нравится goto? Вполне легальный оператор. В случае чего, от него легко избавиться, преобразовав код в конечный автомат (получится цикл с одним switch внутри). Хотя чаще хватает одной дополнительной логической переменной.
И какого типа ограничения? И есть ли ограничение на порядок выдачи перестановок?

UPD. Вот вариант решения на C#. Не самый эффективный, правда.

class Program{
        static IEnumerable<int[]> Permutations(int N,Func<int,int,bool>Cond1,Func<int,int,int,int,bool> Cond2) {
            int[] res=new int[N];
            int k=0;
            res[0]=0;
            while(k>=0){
                if(++res[k]<=N){
                    if(Cond1(k+1,res[k]) && GoodValue(res,k,Cond2)){
                        if(k==N-1) yield return res;
                        else res[++k]=0;
                    }
                }else k--;
            }
        }
        static private bool GoodValue(int[] res,int k,Func<int,int,int,int,bool> Cond) {
            for(int i=0;i<k;i++) {
                if(res[i]==res[k] || !Cond(i+1,res[i],k+1,res[k])) return false;
            }
            return true;
        }

        static int N=6;
        static bool Cond1(int a,int va) {
            if(a==1) return va==1;
            if(a==N) return va==N;
            return true;
        }
        static bool Cond2(int a,int va,int b,int vb) { 
            return Math.Abs(a-b)>1 || Math.Abs(va-vb)<=3;
        }
        static void Main(string[] args) {
            foreach(int[] perm in Permutations(N,Cond1,Cond2))
                Console.WriteLine(String.Join(",",perm));
        }
    }

Функции Permutations передаются два условия. Первое Cond1(a,va) проверяет, может ли элемент va находиться в позиции a, второе Cond2(a,va,b,vb) - могут ли одновременно находиться va в позиции a и vb в позиции b.
В качестве примера - печать перестановок из задачи про лягушку из ProjectEuler: https://projecteuler.net/problem=490
Для N=6 выдаёт ожидаемые 14 перестановок:

1,2,3,4,5,6
1,2,3,5,4,6
1,2,4,3,5,6
1,2,4,5,3,6
1,2,5,3,4,6
1,2,5,4,3,6
1,3,2,4,5,6
1,3,2,5,4,6
1,3,4,2,5,6
1,3,5,2,4,6
1,4,2,3,5,6
1,4,2,5,3,6
1,4,3,2,5,6
1,4,5,2,3,6

Если не нравится конструкция yield return - вставьте вместо неё свою обработку перестановки, а функцию опишите, как void. Если из GoodValue yбрать проверку res[I]==res[k], то вместо перестановок будут печататься все N-элементные наборы из чисел 1..N, удовлетворяющие условию.

Comments

[readical]

Для каждых двух элементов должно быть истинно определенное арифметико-логическое выражение.

[Mrrl]

Написал решение

[readical]

Спасибо. Буду разбираться.

Приведите, пожалуйста, примеры преобразования goto -> switch

[Mrrl]

readical: Например, возьмём такую программу (возможно, она считает число N-элементных неубывающих наборов чисел от 0 до M-1 - я её не проверял):

long NSets(int N){
   long C=0;
   int[] res=new int[N];

   k=-1;
_forward:
   if(++k==N){
     C++; goto _backward;
   }
   res[k]=k==0 ? 0 : res[k-1];
   goto _forward;
_backward:
   if(--k<0) return C;
   if(++res[k]>=M) goto _backward;
   goto _forward;
}

Она преобразуется во что-то такое:

long NSets(int N){
   const int FORWARD=0;
   const int BACKWARD=1;
   const int RETURN=2;

   long C=0;
   int[] res=new int[N];
   k=-1;
   int state=FORWARD;
   while(state!=RETURN){
      swtich(state){
         case FORWARD:
            if(++k==N){
              C++; state=BACKWARD;
            }else{
              res[k]=k==0 ? 0 : res[k-1];
            }
            break;
         case BACKWARD:
            if(--k<0) state=RETURN;
            else if(++res[k]<M) state=FORWARD;
            break;
      }
   }
   return C;
}

Преобразования довольно очевидны.
Пример, конечно, слишком простой - нет ни одного goto изнутри цикла, часть между двумя goto можно оформить, как else... В более сложных случаях придётся сначала расписать циклы через goto, а уже потом преобразовывать в state-машину.