制限付きポイントセットをどのように並べ替えますか？

Question

私は、奇数の位置nのすべての点が位置（n-1）の点の前に出現できないという制限でJavaの点の集合を置換しようとしています。すなわち、2点1と2を与えられたとき、 1,2,3 & 4順列と与えられたポイントのいずれかで、予想される順列のセットは、次のとおりです。

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,3,2,4 
1,3,4,2 
3,1,2,4 
3,4,1,2 
3,1,4,2 

私は現在、順列を見つけるための次のコードを持っています出力は：

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; 
    } 
}