I've used a simpler algorithm, basically what Wikipedia calls "Knuth shuffles". From Wikipedia: ----- unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m */ void initialize_and_permute(unsigned permutation[], unsigned n) { unsigned i; for (i = 0; i < n; i++) { unsigned j = uniform(i); permutation[i] = permutation[j]; /* Swap an existing element [j] to position [i] */ permutation[j] = i; /* ...and put newly-initialized element [i] in position [j] */ } } ----- —Dan
On Mar 25, 2016, at 10:59 AM, rcs@xmission.com wrote:
There's a standard way of generating a random permutation of N objects, equally applicable to 1-1 mapping a factorial-base representation to permutations:
You build the permutation in an array A, indexed from 0...(N-1). Initially, Ai=i. Generate your random integer in the range 0...(N!-1) and convert it to factorial base. Or, generate a sequence of random integers in the ranges [0,1],[0,2],...,[0,N-1]. Use the factorial-base digits from right-to-left (low order digit first), or the random sequence from [0,1] to [0,N-1].
With i running from 1 to N-1, process each digit as a swap instruction for Ai, that says to swap Ai with A_digit. The first instruction says to swap A1 with either A0 or A1, with the latter being a no-op. The last instruction says to swap A[N-1] with any element of A, including a 1/N chance of self-swap-noop.
This is easily converted to the functional composition form in Henry's message below. I'll guess that there's no way to make an additive or multiplicative version of the permutation polynomials, but it's only a guess.
Note that f(x)=x+1 is the permutation (0123...N-1).
Rich
------ Quoting Henry Baker <hbaker1@pipeline.com>:
I'm still wondering if there are simple correspondences between factorial representations and permutation polynomials.
For simplicity, let's focus only on a prime # of elements.
For example, over GF(p) there are p! permutations.
Is there a polynomial form in which we have exactly p choices for one of the coefficients, exactly p-1 choices for the next coefficient, exactly p-2 choices for the next coefficient, and so on?
What if the p basis functions are things other than monomials x, x^2, x^3, etc. ?
With function composition, we can do the following:
f(g(h(...(q(x))...))) can be a representation of one of these p! permutations if
f(x) chooses one of p elements; g(x) chooses one of p-1 elements; h(x) chooses one of p-2 elements, and so forth.
A form such as this should be relatively easy to manufacture.
So it should be possible to represent any permutation in this fully-nested "standard" form.
Are there forms involving multiplication instead of composition?
Are there forms involving addition instead of composition?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun