CODEWITHSUNDEEP
javaarrayssethashset
Iann Wu
Iann Wu

Reputation: 155

Generate a sequence of all permutation of some range of numbers part II

As a follow up to Generate a sequence of all permutation of some range of numbers, I have written the following code inside a Perm class:

/**
 * Permute A to its next permutation, if possible. Returns true if there is
 * such a permutation, and false otherwise.
 */
static boolean nextPerm(int[] A) {
    int N = A.length;
    int k = N - 1;
    int v;
    Set<Integer> S = new HashSet<Integer>();

    while (k >= 0) {
        int max = Collections.max(S);
        if (max > A[k]) {
            v = Collections.min(S);
            S.remove(v);
            S.add(A[k]);
            A[k] = v;
            int [] sArr = convertToArray(S);
            for (int i = k + 1; i < N - 1; i += 1) {
                A[i] = sArr[i - k - 1];
            }
            return true;      
        } else {
            S.add(A[k]);
            k -= 1;
        }
    }
    return false;
}

static int [] convertToArray (Set<Integer> s) {
    int [] sArr = new int[s.size()];
    int index = 0;
    for(Integer i : s) {
        sArr[index++] = i;
    }
    Arrays.sort(sArr);
    return sArr;
}

Basically, what it does is to generate a sequence of all permutation of some range of numbers, as follow:

Let A be a sequence of integers 0 to N-1 in ascending order 
(let's assume its an array of int[N]).    

next_permutation(A):
    k = N-1
    S = { }
    while k >= 0:
        if S contains a value larger than A[k]:
            v = the smallest member of S that is larger than A[k]
            remove v from S
            insert A[k] in S
            A[k] = v
            A[k+1:N-1] = the values in S in ascending order.
            return true
        else:
            insert A[k] in S
            k -= 1
    return false

My code doesn't seem to work tho. Can anyone shed some lights please? Thanks!

UPDATE: After taking the inputs from everyone and work on the problem for a bit, I was able to make it work! There are a couple things I've learned:

  1. As mentioned by Worakam, TreeSet(compared to HashSet) comes in very handy in this question as it is sorted and has the higher() function.
  2. Originally I thought turning a TreeSet into an Integer array would be hectic since the Integer objects aren't quite int. However, it turns out that(probably due to autoboxing/unboxing post java5), I was able to treat the elements within the Integer array as normal int and add int items to it(as shown in the for loop).

Here is the working code:

static boolean nextPerm(int[] A) {
    int N = A.length;
    int k = N - 1;
    int v;
    int max = 0;

    TreeSet<Integer> S = new TreeSet<Integer>();

    while (k >= 0) {
        if (!S.isEmpty() && S.last() > A[k]) {
            v = S.higher(A[k]);
            S.remove(v);
            S.add(A[k]);
            A[k] = v;
            Integer [] sArr = new Integer[S.size()];
            S.toArray(sArr);

            for (int i = k + 1; i < N; i += 1) {
                A[i] = sArr[i - k - 1];
            }
            return true;
        } else {
            S.add(A[k]);
            k -= 1;
        }
    }
    return false;
}

Thanks alot everyone!!

Upvotes: 0

Views: 521

Answers (1)

Worakarn Isaratham
Worakarn Isaratham

Reputation: 1034

First, Collections.max(S) throws NoSuchElementException when the set is empty.

Second, picking the least member of S is not the correct way to implement "the smallest member of S that is larger than A[k]".

I suggest that instead of using a HashSet, you should use a sorted data structure, such as a java.util.TreeSet. It would eliminate the need to sort the set yourself. And the method higher() could be pretty useful for your need.

Upvotes: 1

Related Questions