fast algorithm

kev82 · 08-08-2004, 11:42 AM

ok, i need a fast function to assign permutations of n objects uniqely to integers. my first choice is obviously something like:

Code:

int perm(vector<int> v)
{
    vector<int> w;

    w=v;
    sort(w.begin(), w.end());
    for(int n=0;w!=v;n++) {
	next_permutation(w.begin(), w.end());
    }
    return n;
}

but this has possibly O(N!) with N=v.size(), ie very bad, after playing with it for a while i came up with the following, it recursivly calculates a lower bound for the permutation number using the 1st object until v.size()=1 and the lower bound has converged to the value.

Code:

#include <iostream>
#include <algorithm>
#include <vector>

typedef unsigned int uint;
typedef std::vector<int> vint;
using std::sort;
using std::cout;

uint factorial(int n) {
	switch(n) {
		case 0: return 1;
                case 1: return 1;
                //i'll leave this to your imagination
                default:
		cout << "factorial out of bounds";
		exit(1);
	}
}

void reorder(vector<int> &v) {
	vint w=v, x;

	sort(w.begin(), w.end());
	for(int i=0;i<v.size();i++) {
		for(int j=0;j<w.size();j++) {
			if(w[j]==v[i]) {
				x.push_back(j+1);
				w[j]=-1; //if v has elements the same assign the lowest permutation
				break;
			}
		}
	}
	v=x;
}

uint assign(const vint &v) {
	if(v.size()==1) return 0;

	vint temp=v;
	int s=temp.size();
	reorder(temp);
	return (temp[0]-1)*factorial(s-1) + assign(vint(temp.begin()+1,temp.end()));
}

now assign() apears to be O(N) which is much better but id prefer a non-recursive solution if anyone can come up with one.

my questions:

a) As im gonna be calling assign() in the order of 10^5 times per run would i get much efficiency from implementing it as a lookup table for v.size()<=[suitable number here]?

b) before i can use it i'll need to prove that assign() is a bijective map between a permutation of N distinct elements(v) and an integer betwwen 0 and N! -1 (return value) how would i do this other than just explain how i derived it?

i do not want suggestions on how to improve the code as its not gonna be implemented in c++, i only chose this as a language of convienience(sp?) because most of the board member know it. however any suggestions to improve the algorithm would be great.

if anyone knows a website or group where i would be more likely to get a good response then also please let me know

Hano · 08-09-2004, 10:14 PM

you might want to try on the GDAlgorithms mailing list or newsgroups search (if you dont have newserver use google interface)

dakensta · 08-10-2004, 05:56 AM

Quote:

ok, i need a fast function to assign permutations of n objects uniqely to integers.

If you sort your inital sequence into lexicographical order, then you already have your index, from order (0) -> reverse order (N!-1).

This is what next_permutation is doing anyway

... it just gives the next lexicographical permutation.

The only challenge is to go from index -> permutation and back again, if you need it (I kind of assumed this).

Recursive functions, to coin a phrase, really bake my noodle, but I think that you are basically doing this already in your second code sample.

However, there is a clear explanation of this on comp.programming - http://tinyurl.com/6nzj6 (googlegroups) and I don't think I would do it justice to try and re-interpret it here. The author states O(N^2), rather than O(N), but see implementation note at the bottom, and uses a non-recursive function (loop <---> recursive anyway, no?)

For:

a) Depends - are you using lots of different sequences or just one? how long are they? In my opinion, generally I enumerate as much as possible given that memory is cheap and my patience thin, but also how much efficiency is a genuine concern (to be honest. very rarely, beyond practical constraints, for me) over a working algorithm.

b) If you need it, I imagine that proof of a unique lexicographical order is available on google ... ask a friendly mathematician ... I still don't quite understand why "because it looks like it should" doesn't count as proof *sigh*

Bear in mind that I don't have (much) formal education in CS or Maths, mostl of the stuff I know is derived from empirical experience, so I hope this isn't shooting too low for you.

Anyway, HTH - even if it doesn't. it was an interesting read for me

kev82 · 08-10-2004, 07:09 AM

my alogorithm is O(n)*O(reorder) making it O(n^3) i forgot i was calling reorder(), ive looked at the code but ive found a better solution already because i dont need to map the permutations to the integers in lexographical order, any bijective map will do, so i found the following in Knuth(great book btw)

Code:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <set>
#include <sstream>

using namespace std;

int assign(vector<int> v)
{
    int f=0;

    for(int r=v.size()-1;r>0;r--) {
        int m=*max_element(v.begin(), v.begin()+r+1);
        int s;
        for(s=0;v[s]!=m;s++);
        swap(v[s],v[r]);
        f=f*(r+1)+s;
    }

    return f;
}

//testing code
int main(int argc, char **argv)
{
    vector<int> v;
    set<int> output;
    istringstream iss(argv[1]);
    int n;

    iss >> n;

    for(int i=0;i<n;i++) v.push_back(i);
    sort(v.begin(), v.end()); //not necessary but why not.

    do {
        output.insert(assign(v));
    } while(next_permutation(v.begin(), v.end()));

    cout << output.size() << endl; //should hopefully contain n! unique things.
    return 0;
}

its easy to prove its bijective as the algorithm runs backwards. although the order of it isnt great the time per step is very small so i think its faster than mine, i'll try some speed tests on the mainframe i'll be running it on once i code them to fortran.

is there a most obfuscated way to calculate N! competition cos if there is id like to enter the above code, lol