Как переставить набор точек с ограничениями?

Question

Я пытаюсь переставить набор точек в java с ограничением, что все точки в нечетном положении n не могут появиться перед точкой в ​​позиции (n-1), т. Е. С учетом двух точек 1 и 2, 2 не может появиться до 1 в любой из перестановок и заданных точек 1,2,3 & 4, множество ожидаемых перестановок являются:

1,2,3,4 
1,3,2,4 
1,3,4,2 
3,1,2,4 
3,4,1,2 
3,1,4,2 

настоящее время у меня следующий код для нахождения перестановок:

static void permute(int[] a, int k,int[] p) { 
    if (k == a.length) { 
     for (int i = 0; i < a.length; i++) { 
      System.out.print(" " + a[i]); 
     } 
     System.out.println(); 
    } 
    else { 
     int temp; 
     for (int i = k; i < a.length; i++) { 
      if(i % 2 == 0){ 
       temp = a[k]; 
       a[k] = a[i]; 
       a[i] = temp; 
       permute(a, k + 1,p); 
       temp = a[k]; 
       a[k] = a[i]; 
       a[i] = temp; 
      } 
      else{ 
       if(k > p[i]){ 
        temp = a[k]; 
        a[k] = a[i]; 
        a[i] = temp; 
        permute(a, k + 1,p); 
        temp = a[k]; 
        a[k] = a[i]; 
        a[i] = temp; 
       } 
      } 
     } 
    } 
} 

, но мой ток выход:

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 3 2 
1 4 2 3 
3 2 1 4 
3 2 4 1 
3 1 2 4 
3 1 4 2 
3 4 1 2 
3 4 2 1 

Любая помощь будет очень ценна :-)

Answer 1

насчет рекурсивного подхода?

Просто отрежьте рекурсию, как только ваше состояние нарушится.

Answer 2

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

import java.util.ArrayList; 
import java.util.List; 

public class PermutationsExample { 

    static int[] arr = {1,2,3,4}; 
    public static void main(String[] args) { 
     List<List<Integer>> allPermutationList = getAllPermutations(arr); 
     System.out.println("All permutations are :"); 
     System.out.println(allPermutationList); 
     System.out.println(""); 

     List<List<Integer>> subPermutationList = getRestrictedPermutations(allPermutationList); 
     System.out.println("Permutations with restrictions are:"); 
     System.out.println(subPermutationList); 
    } 

    // see http://www.programcreek.com/2013/02/leetcode-permutations-java/ for further info 

    public static List<List<Integer>> getAllPermutations(int[] num) { 
     List<List<Integer>> result = new ArrayList<>(); 
     result.add(new ArrayList<>()); 
     for (int i = 0; i < num.length; i++) { 
      List<List<Integer>> current = new ArrayList<>(); 
       for (List<Integer> l : result) { 
        for (int j = 0; j < l.size()+1; j++) { 
         l.add(j, num[i]); 
         List<Integer> temp = new ArrayList<>(l); 
         current.add(temp); 
         l.remove(j); 
        } 
       } 
      result = new ArrayList<>(current); 
     } 
     return result; 
    } 

    public static List<List<Integer>> getRestrictedPermutations(List<List<Integer>> listofList){ 
     List<List<Integer>> result = new ArrayList<>(); 
     for(List<Integer> list: listofList){      
      if(isRestrictionRespected(list)){ 
       result.add(list); 
      }    
     }   
     return result; 
    } 

    public static boolean isRestrictionRespected(List<Integer> list){ 
     boolean result = true; 
     for (int i = 1; i < arr.length; i+=2) {    
       if(list.indexOf(arr[i])<list.indexOf(arr[i-1])){ 
       result = false; 
       break; 
       } 
      } 
     return result; 
    } 
}