无"duplicate"解决方案的阵列排列

Question

路由被描述为[1，2，4]。对于路线[1，2，4]，重复的解决方案为[4，3，2，1]。我可以打印数组的所有排列，但我如何提取"唯一"的路由。

permute(java.util.Arrays.asList(1,2,3,4), 0);

static void permute(java.util.List<Integer> arr, int k){
for(int i = k; i < arr.size(); i++){
java.util.Collections.swap(arr, i, k);
permute(arr, k+1);
java.util.Collections.swap(arr, k, i);
}
if (k == arr.size() -1){
System.out.println(java.util.Arrays.toString(arr.toArray()));
}
}

Answer 1

如果你的意思是[1,2,3,4]=[4,3,2.1]=[1,3,2,4]=。。。，

1( 在ArrayList 中变换每个排列

2( 按自然排序顺序对每个排列进行排序

3( 添加在集合中排序的所有排列

Answer 2

我认为这样的"路径"可以描述为"跳"的列表，即相邻点的元组。因此CCD_ 1可以变成CCD_。现在，如果您使用较小的值构建元组，那么第一个4,3,2,1将变成[3,4],[2,3],[2,1]——正如您所看到的，这将是与1,2,3,4相同的元组。因此，如果一个排列具有任何顺序的相同元组(即元组集(，则它将等于另一个排列。

使用它，您可以构建一个Map<Set<Tuple>, List<ArrayList<Integer>>>来获取具有相同"跃点"的所有路径。只需注意映射键应该是不可变的，所以最好使用真正的不可变集实现，或者至少用Collections.unmodifiableSet()来装饰它。

这里有一个可能使用的Tuple类：

class Tuple {
private int l,r;
public Tuple( int a, int b ) {
if ( a > b ) {
l = b;
r = a;
} else {
l = a;
r = b;
}
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + l;
result = prime * result + r;
return result;
}
@Override
public boolean equals( Object obj ) {
if( this == obj ) return true;
if( obj == null ) return false;
if( getClass() != obj.getClass() ) return false;
Tuple other = (Tuple) obj;
if( l != other.l ) return false;
if( r != other.r ) return false;
return true;
}
@Override
public String toString() {
return "[" + l + ", " + r + "]";
}       
}

然后将Map<Set<Tuple>, List<List<Integer>>>传递给1,2,3,40并填充：

static void permute(List<Integer> arr, int k, Map<Set<Tuple>, List<List<Integer>>> results){
for(int i = k; i < arr.size(); i++){
Collections.swap(arr, i, k);
permute(arr, k+1, results);
Collections.swap(arr, k, i);
}
if (k == arr.size() -1){
Set<Tuple> path = new HashSet<>();
for( int i = 0; i < arr.size() - 1; i++ ) {
path.add( new Tuple(arr.get( i ), arr.get( i + 1 )) );
}
results.computeIfAbsent( Collections.unmodifiableSet( path ), v -> new ArrayList<List<Integer>>() ).add( new ArrayList<>( arr ) );
}
}

使用地图，你可以得到所有共享相同"跳跃"的排列。在你的情况下，从开始到结束或返回基本上只有一条直线，只有两个相等的排列。