二维数组的java置换

3 周 Questions & Answers 1158

下面是关于排列的另一个问题。我已经尽我所能把我的问题尽可能好地表述出来。如果你有什么不明白的地方，请随时提问

我有一个列表，包含一个列表，包含一个列表，包含一个符号

List<List<List<Symbol>>> list = new ArrayList<List<List<Symbol>>>();

symbol类只接受一个值，并跟踪我正在创建的内容的一些重要特性。结构中的所有符号彼此不同

然而，以各种不同的方式切换位置存在一些困难，因为

第一个列表是整个事情的包装。它包含两个包含符号的列表的分组。这是因为当包含在分组中时，符号不应该彼此分离

第二个列表的长度始终为2，每个列表包含一个唯一符号列表。至于为什么是二，不要问我这个问题。如果这个程序能够同时处理长度超过两个的列表，那就太好了

第三个列表包含所有符号，如上所述，每个包装器有两个符号

我想要的是生成所有可能的排列并分析它们。也就是说，我希望符号切换到所有可能的组合，同时仍包含在其各自的列表中

这可能看起来像这样（用伪代码编写，描述上面提到的类似列表的结构）

[[a, b, c], [d, e, f]], [[g, h, i, j], [k, l, m, n]], [[o, p], [q, r]], [[s, t, u], [v, x, y]],

下面是一个例子，说明（可能有数千种）排列中的一种可能是什么

[[c, a, b], [d, f, e]], [[g, h, j, i], [k, l, m, n]], [[o, p], [q, r]], [[s, t, u], [v,y, x]],

到目前为止，我尝试的是将它们放入一个好的传统排列方法中，该方法适用于单个数组（或列表，如果您愿意的话），并尝试将其修改为使用多维数组。当然，有一种简单的好方法可以做到这一点，最好使用递归。如果有没有办法，那完全没关系

再一次，如果你有任何问题以上我刚刚写的，请随时发表评论

亲切问候,

# 1 楼答案

这里是一个递归解决方案permutationsList可以获取任意维数的列表。顺便说一句，你给出的例子有近300万个排列。我的程序需要几秒钟来计算所有这些

import java.util.*;

public class Perm {
  static <T> List<List<T>> permutations(List<T> list) {
    if(list.isEmpty()) return new LinkedList<>();
    List<List<T>> result = new LinkedList<>();
    for(int i = 0; i < list.size(); i++) {
      T elem = list.get(i);
      List<T> copy = new LinkedList<>(list);
      copy.remove(i);
      List<List<T>> permRest = permutations(copy);
      if(permRest.isEmpty()) permRest.add(new LinkedList<>());
      for(List<T> perm: permRest) {
        List<T> permCopy = new LinkedList<>(perm);
        permCopy.add(0, elem);
        result.add(permCopy);
      }
    }
    return result;
  }

  @SuppressWarnings("unchecked")
  static List<List> permutationsLists(List list) {
    if(list.size() == 0) {
      return new LinkedList<>();
    } if(!(list.get(0) instanceof List)) {
      return permutations(list);
    } else {
      List<List> permutationsFirst = permutationsLists((List)list.get(0));
      List<List> permutationsRest = (List<List>)permutationsLists(list.subList(1, list.size()));
      if(permutationsRest.size() == 0) permutationsRest.add(new LinkedList());
      List<List> result = new LinkedList<>();
      for(List pf: permutationsFirst) {
        for(List pr: permutationsRest) {
          List copy = new LinkedList(pr);
          copy.add(0, pf);
          result.add(copy);
        }
      }
      return result;
    }
  }

  public static void main(String[] args) {
    /*
    List<List<List<String>>> list = Arrays.asList(
      Arrays.asList(Arrays.asList("a", "b", "c"), Arrays.asList("d", "e", "f")),
      Arrays.asList(Arrays.asList("g", "h", "i", "j"), Arrays.asList("k", "l", "m", "n")),
      Arrays.asList(Arrays.asList("o", "p"), Arrays.asList("q", "r")),
      Arrays.asList(Arrays.asList("s", "t", "u"), Arrays.asList("v", "w", "x"))
    );
    */
    List<List<Integer>> list = Arrays.asList(Arrays.asList(1,2,3), Arrays.asList(4,5));
    System.out.println(permutationsLists(list));
  }
}

编辑：下面是一个使用流的解决方案。它非常高效，可以在不占用太多内存的情况下生成大量排列。顺便说一句，您可以使用iterator()方法将流转换为迭代器

import java.util.*;
import java.util.stream.Stream;
import java.util.stream.IntStream;

public class Perm {

  static <T> Stream<List<T>> permutations(List<T> list) {
    if(list.isEmpty()) return Stream.empty();
    return IntStream.range(0, list.size()).boxed().flatMap(i -> {
      T elem = list.get(i);
      List<T> copy = new LinkedList<>(list);
      copy.remove((int)i);
      Stream<List<T>> permRest = copy.isEmpty()?Stream.of(new LinkedList<>()):permutations(copy);
      return permRest.map(perm -> {
        List<T> permCopy = new LinkedList<>(perm);
        permCopy.add(0, elem);
        return permCopy;
      });
    });
  }

  @SuppressWarnings("unchecked")
  static <T> Stream<List<T>> permutationsLists(List<T> list) {
    if(list.size() == 0) {
      return Stream.empty();
    } if(!(list.get(0) instanceof List)) {
      return permutations(list);
    } else {
      List rawList = list;
      Stream<List> permutationsFirst = permutationsLists((List)list.get(0));

      return permutationsFirst.flatMap(pf -> {
        Stream<List> permutationsRest = list.size() < 2?Stream.of(new LinkedList()):permutationsLists(rawList.subList(1, list.size()));
        return permutationsRest.map(pr -> {
          List<T> copy = new LinkedList<>(pr);
          copy.add(0, (T)pf);
          return copy;
        });
      });
    }
  }

  public static void main(String[] args) throws Exception {
    List<List<List<String>>> list = Arrays.asList(
      Arrays.asList(Arrays.asList("a", "b", "c"), Arrays.asList("d", "e", "f")),
      Arrays.asList(Arrays.asList("g", "h", "i", "j"), Arrays.asList("k", "l", "m", "n")),
      Arrays.asList(Arrays.asList("o", "p"), Arrays.asList("q", "r")),
      Arrays.asList(Arrays.asList("s", "t", "u"), Arrays.asList("v", "w", "x"))
    );

    Stream<List<List<List<String>>>> result = permutationsLists(list);
    result.forEach(p -> System.out.println(p));
  }
}

Python中文网

有 Java 编程相关的问题?

二维数组的java置换

共 (1) 个答案

# 1 楼答案