Algorithme d'imprimer une liste mélangée, sur place et avec O (1) mémoire

essentiellement ce dont vous avez besoin est un générateur de nombres aléatoires qui produit les chiffres 0..n-1 exactement une fois chacun.

Voici une idée à moitié cuit au four: vous pouvez faire assez bien en cueillant un premier p légèrement plus grand que N, puis choisissez un X aléatoire entre 1 et P-1 dont l'ordre dans le groupe multiplicatif MOD P est P-1 (choix XS et test aléatoires que ceux qui satisfont x ^ i! = 1 pour i = n et cela vous donne une séquence d'index à imprimer.

Ce n'est pas terriblement aléatoire, mais vous pouvez utiliser la même technique à plusieurs reprises, en suivant les index ci-dessus (+1) et les utiliser comme des exposants d'un autre générateur X2 Modulo Authore P2 (vous aurez besoin de n

Ma solution dépend des propriétés mathématiques de certains numéros intelligemment calculés xxx pré>

avec cette configuration, nous pouvons calculer les suivants à plusieurs reprises et il ira tous les éléments de la matrice exactement une fois dans un apparemment aléatoire. ordre, après quoi il se bougera de traverser la matrice dans la même commande exacte à nouveau. p> xxx pré>

J'ai mis en œuvre et testé cela dans Java, j'ai donc décidé de coller mon code ici pour Référence future. P>

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class PseudoRandomSequence {

    private long            state;
    private final long  range;
    private final long  root;
    private final long  prime;
    //Debugging counter
    private int             dropped = 0;

    public PseudoRandomSequence(int r) {
        range = r;
        prime = closestPrimeAfter(range);
        root = modPow(generator(prime), closestPrimeTo(prime / 2), prime);
        reset();
        System.out.println("-- r:" + range);
        System.out.println("   p:" + prime);
        System.out.println("   k:" + root);
        System.out.println("   s:" + state);
    }

    // https://en.wikipedia.org/wiki/Primitive_root_modulo_n
    private static long modPow(long base, long exp, long mod) {
        return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).intValue();
    }

    //http://e-maxx-eng.github.io/algebra/primitive-root.html
    private static long generator(long p) {
        ArrayList<Long> fact = new ArrayList<Long>();
        long phi = p - 1, n = phi;
        for (long i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                fact.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) fact.add(n);
        for (long res = 2; res <= p; ++res) {
            boolean ok = true;
            for (long i = 0; i < fact.size() && ok; ++i) {
                ok &= modPow(res, phi / fact.get((int) i), p) != 1;
            }
            if (ok) {
                return res;
            }
        }
        return -1;
    }

    public long get() {
        return state - 1;
    }

    public void advance() {
        //This loop simply skips all results that overshoot the range, which should never happen if range is a prime number.
        dropped--;
        do {
            state = (state * root) % prime;
            dropped++;
        } while (state > range);
    }

    public void reset() {
        state = root;
        dropped = 0;
    }

    private static boolean isPrime(long num) {
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }

    private static long closestPrimeAfter(long n) {
        long up;
        for (up = n + 1; !isPrime(up); ++up)
            ;
        return up;
    }

    private static long closestPrimeBefore(long n) {
        long dn;
        for (dn = n - 1; !isPrime(dn); --dn)
            ;
        return dn;
    }

    private static long closestPrimeTo(long n) {
        final long dn = closestPrimeBefore(n);
        final long up = closestPrimeAfter(n);
        return (n - dn) > (up - n) ? up : dn;
    }

    private static boolean test(int r, int loops) {
        final int array[] = new int[r];
        Arrays.fill(array, 0);
        System.out.println("TESTING: array size: " + r + ", loops: " + loops + "\n");
        PseudoRandomSequence prs = new PseudoRandomSequence(r);
        final long ct = loops * r;
        //Iterate the array 'loops' times, incrementing the value for each cell for every visit. 
        for (int i = 0; i < ct; ++i) {
            prs.advance();
            final long index = prs.get();
            array[(int) index]++;
        }
        //Verify that each cell was visited exactly 'loops' times, confirming the validity of the sequence
        for (int i = 0; i < r; ++i) {
            final int c = array[i];
            if (loops != c) {
                System.err.println("ERROR: array element @" + i + " was " + c + " instead of " + loops + " as expected\n");
                return false;
            }
        }
        //TODO: Verify the "randomness" of the sequence
        System.out.println("OK:  Sequence checked out with " + prs.dropped + " drops (" + prs.dropped / loops + " per loop vs. diff " + (prs.prime - r) + ") \n");
        return true;
    }

    //Run lots of random tests
    public static void main(String[] args) {
        Random r = new Random();
        r.setSeed(1337);
        for (int i = 0; i < 100; ++i) {
            PseudoRandomSequence.test(r.nextInt(1000000) + 1, r.nextInt(9) + 1);
        }
    }

}