java - 如何排列一组有限制的点？

Question

我正在尝试置换 java 中的一组点，限制是奇数位置 n 中的所有点都不能出现在位置 (n-1) 中的点之前，即给定 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

您可能首先找到所有排列，然后仅过滤那些遵守限制的排列。下面是一个例子:

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