제한이있는 점 집합을 어떻게 바꾸는가?

Question

이상한 위치 n의 모든 점이 위치 (n-1)의 점 앞에 나타날 수 없다는 제한하에 java의 점 집합을 바꾸려고합니다. 즉, 2 점 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; 
    } 
}