Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

77
LINES

< > BotCompany Repo | #1010346 // allPermutations_iterator - return all permutations of a list as iterator [v2]

JavaX fragment (include)

static <A> IterableIterator<O[]> allPermutations_iterator(final L<A> theList) {
  ret new IterableIterator<O[]>() {
    int[] next;

    int n = l(theList);
    int[] perm, dirs;

    {
        if (n > 0) {
            perm = new int[n];
            dirs = new int[n];
            for(int i = 0; i < n; i++) {
                perm[i] = i;
                dirs[i] = -1;
            }
            dirs[0] = 0;
        }

        next = perm;
    }

    @Override
    public O[] next() {
        int[] r = makeNext();
        next = null;
        O[] out = new O[n];
        for i to n:
          out[i] = theList.get(r[i]);
        ret out;
    }

    @Override
    public boolean hasNext() {
        return (makeNext() != null);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    int[] makeNext() {
        ping();
        if (next != null)
            return next;
        if (perm == null)
            return null;

        // find the largest element with != 0 direction
        int i = -1, e = -1;
        for(int j = 0; j < n; j++)
            if ((dirs[j] != 0) && (perm[j] > e)) {
                e = perm[j];
                i = j;
            }

        if (i == -1) // no such element -> no more premutations
            return (next = (perm = (dirs = null))); // no more permutations

        // swap with the element in its direction
        int k = i + dirs[i];
        swapIntArray(dirs, i, k);
        swapIntArray(perm, i, k);
        // if it's at the start/end or the next element in the direction
        // is greater, reset its direction.
        if ((k == 0) || (k == n-1) || (perm[k + dirs[k]] > e))
            dirs[k] = 0;

        // set directions to all greater elements
        for(int j = 0; j < n; j++)
            if (perm[j] > e)
                dirs[j] = (j < k) ? +1 : -1;

        return (next = perm);
    }
  };
}

Author comment

Began life as a copy of #1010342

download  show line numbers  debug dex  old transpilations   

Travelled to 14 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, onxytkatvevr, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt

Comments [hide]

ID Author/Program Comment Date
1327 stefan https://stackoverflow.com/questions/2000048/stepping-through-all-permutations-one-swap-at-a-time/11916946#11916946 2017-09-12 03:04:38

add comment

Snippet ID: #1010346
Snippet name: allPermutations_iterator - return all permutations of a list as iterator [v2]
Eternal ID of this version: #1010346/9
Text MD5: a7a12fa00e0364fce0fb161a32a23839
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2019-07-15 02:39:23
Source code size: 1985 bytes / 77 lines
Pitched / IR pitched: No / No
Views / Downloads: 758 / 803
Version history: 8 change(s)
Referenced in: #1006654 - Standard functions list 2 (LIVE, continuation of #761)