获取整数列表的所有子列表的所有排列 [英] Getting ALL permutations of ALL sublists of a list of integers

问题描述

我一直在遇到这个问题。基本上，我有一个整数列表，例如

I've been having trouble with this problem. Basically, I have a list of integers, such as

list = [1, 2, 3]

我想获取每个子集的所有可能排列。我知道在线上也存在类似的问题，但是我找不到一个可以完成所有排列以及每个子集的问题。换句话说，我想要：

I want to get all possible permutations of every subset. I know similar questions exist online, but I couldn't find one that does every permutation as well as every subset. In other words, I want:

function(list) = 
[], [1], [2], [3],
[1, 2], [2, 1], [1, 3], [3,1], [2, 3], [3,2],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

我知道即使输入列表很小，输出也会变得非常大。不幸的是，我只是无法弄清楚如何解决这个问题。

I understand the output will get extremely large even for a small input list size. Unfortunately, I just cannot figure out how to do such a problem.

谢谢！

推荐答案

我最终使用了这两个功能的组合。不知道它是否按预期工作，但是到目前为止它是否已经正常工作。

I ended up using a combination of these two functions. Not sure if it works as intended, but so far it has been working properly.

// Generates all permutations of a set. Thus, given an input like [1, 2, 3] it changes the null
// final_list input to be [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
static void heappermute(List<List<Integer>> waypoints, int n,     List<List<List<Integer>>> final_list) {
    int i;
    if (n == 1) {
        final_list.add(waypoints);
    }
    else {
        for (i = 0; i < n; i++) {
            heappermute(waypoints, n-1, final_list);
            if (n % 2 == 1) {
                swap(waypoints.get(0), waypoints.get(n-1));
        }
            else {
                swap(waypoints.get(i), waypoints.get(n-1));
            }
        }
    }
}

static void swap (List<Integer> x, List<Integer> y)
{
    List<Integer> temp = new ArrayList<>();
    temp = x;
    x = y;
    y = temp;
}


// Generates all subsets of a given set. Thus, given a list of waypoints, it will return a list of 
// waypoint lists, each of which is a subset of the original list of waypoints.
// Ex: Input originalSet = {1, 2, 3}
//     Output: = {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
// Code modified from http://stackoverflow.com/questions/4640034/calculating-all-of-the-subsets-of-a-set-of-numbers 

public static List<List<List<Integer>>> powerSet(List<List<Integer>> originalSet) {
    List<List<List<Integer>>> sets = new ArrayList<>();
    if (originalSet.isEmpty()) {
        sets.add(new ArrayList<List<Integer>>());
        return sets;
    }
    List<List<Integer>> list = new ArrayList<List<Integer>>(originalSet);
    List<Integer> head = list.get(0);
    List<List<Integer>> rest = new ArrayList<List<Integer>>(list.subList(1, list.size()));
    for (List<List<Integer>> set : powerSet(rest)) {
        List<List<Integer>> newSet = new ArrayList<List<Integer>>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }
    return sets;
}

这篇关于获取整数列表的所有子列表的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！