1

以下に示す順列ジェネレーターが与えられました。次のように初期化しましたPermutationGenerator perm = new PermutationGenerator(4);。

関数を複数回使用しようとしていますnext()が、同じ結果が得られ続けます。このコードを適切に使用して順列を生成するにはどうすればよいですか?

int[] try = p.next()

for(int i=0;i<try.length;i++) {
    System.out.println(try[i]);
}

// Generator of all permutations of: 0,1,2,...,n-1

public class PermutationGenerator {
// private data

private int[] perm;
private boolean first;

// constructor

public PermutationGenerator (int n) {
    perm = new int [n];
    first = true;
}


// return the next permutation, or null if no more
// Reference: Wikipedia Permutation 5.2.2

public int[] next () {
    int n = perm.length;

    // starting permutation: 0 1 2 3 ... n-1

    if (first) {
        first = false;
        for (int i = 0 ; i < n ; i++)
            perm [i] = i;
        return perm;
    }

    // construct the next permutation
    // find largest k so that perm[k] < perm[k+1]; if none, finish

    int i, j, k, l;

    for (k = n - 2 ; k >= 0 && perm [k] >= perm [k + 1] ; k--)
        ;
    if (k < 0)
        return null; // no more

    // find largest l so that perm[k] < perm[l]

    for (l = n - 1 ; l >= 0 && perm [k] >= perm [l] ; l--)
        ;

    // swap perm[k] and perm[l]

    swap (perm, k, l);

    // reverse perm[k+1]...perm[n-1]

    for (i = k + 1, j = n - 1 ; i < j ; i++, j--)
        swap (perm, i, j);

    return perm;
}


// swap a[i] and a[j]

private static void swap (int a[], int i, int j) {
    int temp = a [i];
    a [i] = a [j];
    a [j] = temp;
}
}
4

1 に答える 1

1 
import java.util.Random;

public class PermutationGenerator {

    private int[] perm;
    private static Random r = new Random();

    public PermutationGenerator(int n) {
        perm = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = i;
        }
    }

    public int[] next() {
        helper(perm, perm.length);
        return perm;
    }

    private static void helper(int[] a, int length) {
        if (length > 1) {
            swap(a, r.nextInt(length), length - 1);
            helper(a, length - 1);
        }
    }

    private static void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        PermutationGenerator generator = new PermutationGenerator(4);
        int[] perm = generator.next();
        for (int i = 0; i < perm.length; i++) {
            System.out.println(perm[i]);
        }
    }
}

昼休みからわずか 5 分で、上記の動作するコードを書きました。よろしければお試しください。

投稿されたコードに関しては、あまり読みにくく、あまり調べていませんでした。しかし、メソッド内で見つけたすぐに明らかなエラーは、とのnextように比較を使用したことです。perm [k] >= perm [k + 1]perm [k] >= perm [l]

順列を生成するとき、要素間の比較を行うことは絶対に不要であり、間違っていることさえあります。

于 2012-12-06T05:37:59.003 に答える