CODEWITHSUNDEEP
javaalgorithmindexingpermutationbreadth-first-search
Lucas Sousa
Lucas Sousa

Reputation: 352

How to index a large number of permutations?

I'm trying to code a program that finds for the God's Algorithm that solves a particular puzzle -- shortest sequence that leads current state until its solved state.

To do this, I have to map all permutations/states (nodes) with its respectively distances until solved (depth).

I'm using some breadth-first search concepts to get the permutations that puts the puzzle in a different/notVisited permutation and looping this until don't get any new position.

Beyond this, I'm using two algorithms to encode the permutations to a single index and retrieve the permutation back, aiming using this to putz depths values in a array. The following pseudo-code can demonstrate what I'm doing:

Fill table completely with -1
table[pos2idx(theSolvedPermutation)] = 0
depth = 0
loopbegin {
    numOfVisitedPositions = 0
        for (i = 1 to N_PERMUTATIONS) {
            if (table[i] == depth) then {
                for (each available movement m) {
                    current = pos2idx(m applied to idx2pos(i))
                    if (table[current]= -1) then {
                        numOfVisitedPositions++
                        table[current] = depth + 1
                    } endif
                } endfor
            } endif
        } endfor
    depth++
    print numOfVisitedPositions " positions at distance " depth
} loop while numOfVisitedPositions > 0

However, seems there are too many information to be processed using this approach in this mapping/indexing step.

Here is , respectively, the pseudos for pos2idx() and idx2pos() methods:

pos2idx(permutation[])
    index = 0
    for i = 1 to length - 2
        index *= (length - i + 1)
        for j = i + 1 to length
            if permutation[i] > permutation[j] then
                index += 1
        endfor
    endfor
return index

idx2pos(index, length)
    n = length
    perm[n]     = 2
    perm[n - 1] = 1
    sum = 0

    for i = n - 2 to 1
        perm[i] = 1 + (index % (n - i + 1))
        sum += perm[i] - 1
        index/= (n - i + 1)
        for j = i + 1 to n
            if perm[j] >= perm[i] then
                perm[j]++
        endfor
    endfor

    if sum % 2 = 1 then
        swap perm[n] with perm[n - 1]

    return perm

The puzzle have 12 "moving pieces", 8 different movements and parity restriction. This last means that we can't get permutations with a odd number of swaps (e.g. [1,2,4,3,...,12], an valid can be be [1,2,4,3,12,...11]), what I think that can be expressed with the value 12!/2. But, probably in terms of complexity, the algorithm doesn't finishes with this amount of data: my notebook i3 with 6GB ram spent 6 min to get a JavaHeapSizeException hahaha.

I just applied the same approach considering the puzzle have only 8 elements with 4 different movements (then would be 8!/2 permutations) and I successfully reached something like between 130000 and 145000 solutions per second.

Then, there are any hint for how to process/index this amount of permutations in this algorithm or this algorithm can't finish in a large processing like that? Any help is apreciated!

Some reference: - Computer Puzzling - Indexing - Useful Mathematics

Upvotes: 0

Views: 183

Answers (1)

trincot
trincot

Reputation: 350841

One consideration that would lower the number of configurations to look at:

Your current code regards two states to be distinct when they are really the same from a human point of view; this is when you can make the transition by just turning the whole cube. Such a transition does not count as a move, so these two states should be regarded the same. This reduces the number of distinct states by a factor of 12.

You could for instance require that one particular piece always remains at the same coordinate. This would mean you have to redefine some of the available moves so they do not touch this particular piece. For instance, let's say you will keep piece number 12 always fixed at position 12 (it never gets permuted), and that you currently have a move encoded as a permutation of pieces 10, 11, and 12. Then redefine that move as a permutation of pieces 1..9, as if you would first turn the whole cube in the opposite direction of the intended move (around that corner), and then perform the move (bringing back piece 12 into its home slot).

This means you don't have to store anything about piece 12: length can be 11 instead. At the same time your table will be 12 times smaller.

Upvotes: 1

Related Questions