Member Avatar for hamidvosugh

Hi
Would any one tell me how can I generate a random permutation of N numbers in c++?
Is there any algorithm in STL for this purpose?

Thanks in advance

  • 4 Contributors
  • 6 Replies
  • 225 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by hamidvosugh

Dani AI

Generated

Short answer: don't enumerate all permutations. Produce each permutation uniformly at random (Fisher–Yates / std::shuffle) and, if you must avoid repeats, detect duplicates by storing a compact, unique representation (a Lehmer / factorial-number rank) rather than saving every permutation. That keeps memory small and avoids the M! explosion warned about; it also fixes the bias problems in ad-hoc approaches like “stop next_permutation at a random point” (which does not give uniform samples).

Here is a compact pattern you can apply immediately (assumes permutations of 1..n). It generates random permutations with std::shuffle, computes a unique 64-bit Lehmer rank for each sample, and keeps only distinct ones until you have N samples.

#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <unordered_set>

using u64 = unsigned long long;

// compute factorials up to n
std::vector<u64> facts(int n){
    std::vector<u64> f(n+1,1);
    for(int i=2;i<=n;i++) f[i]=f[i-1]*i;
    return f;
}

// Lehmer rank (perm values are 1..n)
u64 lehmer_rank(const std::vector<int>& p, const std::vector<u64>& f){
    int n = p.size();
    std::vector<char> used(n+1,0);
    u64 rank = 0;
    for(int i=0;i<n;i++){
        int smaller = 0;
        for(int v=1; v<p[i]; ++v) if(!used[v]) ++smaller;
        rank += (u64)smaller * f[n-1-i];
        used[p[i]] = 1;
    }
    return rank;
}

// sample N distinct permutations
std::vector<std::vector<int>> sample_unique(int n, int N){
    auto f = facts(n);
    std::mt19937 rng(std::random_device{}());
    std::unordered_set<u64> seen;
    std::vector<std::vector<int>> out;
    while((int)out.size() < N){
        std::vector<int> p(n);
        std::iota(p.begin(), p.end(), 1);
        std::shuffle(p.begin(), p.end(), rng);
        if(seen.insert(lehmer_rank(p,f)).second) out.push_back(std::move(p));
    }
    return out;
}

Notes and cautions:

  • The Lehmer rank fits in 64 bits only up to n = 20 (20! < 2^64). For larger n use hashing or big integers, or avoid exact “no-repeat” guarantees.
  • If N is close to n! and n is small, it’s simpler to enumerate all permutations, shuffle their indices and pick the first N.
  • For extremely large ranges where sampling without replacement must be exact but M is huge, generate N distinct integer ranks without replacement (Floyd’s algorithm) and decode each rank to a permutation (factorial-number decoding). Use a Fenwick/bit tree for faster decode if n is large.
  • Always use std::shuffle/std::mt19937 or std::uniform_int_distribution instead of rand()/% to avoid bias.

Recommended Answers

All 6 Replies

Member Avatar for mrnutty

What sort of premutation? On what set?

Member Avatar for hamidvosugh

What sort of premutation? On what set?

int array[] ={1,2,3,4};
The output of next_permutation() on the above array result in
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
.....
.....
2 4 3 1
...
...
What I like to be output is permutation of those numbers, but in different orders each time the function is called.
E.X
2 4 3 1
1 4 3 2
2 1 3 4
1 2 4 3
3 4 2 1
4 2 1 3
...
...
1 2 3 4

Member Avatar for pecet

You can store all permutations in 2D vector. Then You need to create another vector with M! elements (indexes). Random_shuffle vector with indexes and you have order in which You should read data from 2D vector (with all permutations).
But since (N < M) this algorithm is little overkill, because no matter how big N would be, you always have to generate all permutations.

Edited by pecet because: n/a
Member Avatar for hamidvosugh

I have reached to the following idea which works quite well for me. Although it won't generate all the permutations in the given range.

int array[] = {1,2,3,4,5};
srand (time(0));
do{
}while(next_permutation(array, array +(rand()%5)));

Edited by hamidvosugh because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.