0

I'm new to Java (1month). I've been trying to do the below unsuccessfully, any help would be appreciated. What I'm trying to have is:

  1. Main passes int array to method perm2.
    perm2(new int[]{1,2,3});

  2. perm2 will make permutations of it and add to an ArrayList and return it.

This is what I have so far. As you can see it just prints out the permutations.
Problem is I can't add them to an ArrayList and return. 

public static void perm2(int[] s) {
    int N = s.length;
    int[] a = new int[N];
    for (int i = 0; i < N; i++) a[i] = s[i];
    perm2(a, N);
}
private static void perm2(int[] a, int n) {
    if (n == 1) {
        System.out.println(Arrays.toString(a));
        return;
    }
    for (int i = 0; i < n; i++) {
        swap(a, i, n-1);
        perm2(a, n-1);
        swap(a, i, n-1);
    }
}  
private static void swap(int[] a, int i, int j) {
    int c;
    c = a[i]; a[i] = a[j]; a[j] = c;
}

Output:

[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
[1, 3, 2]
[2, 1, 3]
[1, 2, 3]

I don't really want to output them with sysout. I just want them returned in ArrayList of int arrays.

4

4 回答 4

1

您的第一个 perm2 方法至少应该返回新对象。该代码中未修改原始对象。

  public static int[] perm2(int[] s) {
    int N = s.length;
    int[] a = new int[N];
    for (int i = 0; i < N; i++) a[i] = s[i];
    perm2(a, N);
    return a;
}
private static void perm2(int[] a, int n) {
    if (n == 1) {
        System.out.println(Arrays.toString(a));
        return;
    }
    for (int i = 0; i < n; i++) {
        swap(a, i, n-1);
        perm2(a, n-1);
        swap(a, i, n-1);
    }
 }  
private static void swap(int[] a, int i, int j) {
    int c;
    c = a[i]; a[i] = a[j]; a[j] = c;
}
于 2013-10-15T10:37:14.047 回答
1

使用主要 perm 方法的返回类型List<int[]>（或者您更喜欢ArrayList<int[]>）：

public static List<int[]> perm2(int[] s) {
    List<int[]> permutations = new ArrayList<>();
    perm2(permutations, s.clone(), s.length);
    return permutations;
}

然后在第二种方法中，将列表作为另一个参数传递给它，以便它可以添加每个排列。请注意，它必须克隆数组，否则它将一遍又一遍地添加相同的（更改的）数组对象，最终只会得到最终排列的几个副本的列表。

private static void perm2(List<int[]> permutations, int[] a, int n) {
    if (n == 1) {
        permutations.add(a.clone());
        return;
    }
    for (int i = 0; i < n; i++) {
        swap(a, i, n-1);
        perm2(permutations, a, n-1);
        swap(a, i, n-1);
    }
}

调用它：

List<int[]> permutations = perm2(new int[] { 1, 2, 3 });

for (int[] permutation : permutations) {
    System.out.println(Arrays.toString(permutation));
}

没有必要但您可能会考虑的事情是将第一个 perm2 方法的参数从int[] s更改为int... s。然后你可以简单地调用它perm2(1, 2, 3)而不是perm2(new int[] { 1, 2, 3 })，尽管它仍然会接受显式数组。

于 2013-10-15T10:40:21.027 回答
1

ArrayList 只能保存对象。您可以将包装类 Integer 用于您的 int （原始）值。

于 2013-10-15T10:34:50.947 回答
0

您必须更改方法 perm2 以返回数组和方法的签名。

    public static ArrayList<Integer> perm2(int[] s) {
    ArrayList<Integer> a = new ArrayList<Integer>();
    for (int i = 0; i < a.size(); i++) {
        a.add(s[i]);
    }
    perm2(a, a.size());
    return a;
}
private static void perm2(ArrayList<Integer> a, int n) {
    if (n == 1) {
        return;
    }
    for (int i = 0; i < n; i++) {
        swap(a, i, n - 1);
        perm2(a, n - 1);
        swap(a, i, n - 1);
    }
}
private static void swap(ArrayList<Integer> a, int i, int j) {
    int c;
    c = a.get(i);
    a.add(i, a.get(j));
    a.remove(i + 1);
    a.set(j, c);
}
于 2013-10-15T10:41:55.467 回答