How do I generate 100 randomly selected permutations for an array with 16 elements?

user_18177347 0
Viewed 137

I would like to generate 100 randomly selected permutations for an array with 16 elements.

The array = <1, 2, 3, . . . 16>

void printarray(int A[], int size)
{
    int i, j;
    for(i = 0; i < size; i++)
        cout << endl << A[i];
    cout << endl;
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void permutation(int *A, int start, int end)
{
    if(start == end)
    {
        printarray(A, end + 1);
        return;
    }
    int i;
    for(i = start; i <= end; i++)
    {
        swap((A + i), (A + start));
        permutation(A, start + 1, end);
        swap((A + i), (A + start));
    }
}

I used this to find all the permutations for an array with 4 elements, with the array = <1, 2, 3, 4>. However, I cannot use this to find 100 random permutations for the array with 16 elements.

Additionally, is there a program that I could use to find ALL permutations of the array A = <1, 2, 3, 4> AND only 100 random permutations of another array A = <1, 2, 3, ..., 16>?

permutation arrays c++
2 Answers

This is a brute force approach, but each individual permutation can be stored in an instance of a sequence container allowing only unique values. And, all of the generated permutations can be stored in a set. Then your algorithm would be:

  1. Create empty set of permutations.
  2. Create empty permutation.
  3. Push random values 1-16 into the permutation until its size reaches 16.
  4. Insert permutation into the set.
  5. If the size of the set is less than 100, go back to step (2).

UPDATE:

Here is an implementation that abuses std::unordered_set on coliru.

To do this properly you would need to implement your own container that combines properties of std::vector and std::set.

UPDATE 2:

Here is minimal implementation of unique_sequence container:

template<typename T>
struct unique_sequence
{
    auto size()  const { return v_.size();  }
    auto begin() const { return v_.begin(); }
    auto end()   const { return v_.end();   }

    void push_back(T e)
    {
        auto [ _, ins ] = s_.insert(e);
        if(ins) v_.push_back(std::move(e));
    }

    auto operator<(const unique_sequence<T>& rhs) const { return v_ < rhs.v_; }

private:
    std::vector<T> v_;
    std::set<T> s_;
};

You can use it to store individual permutations and the entire set of permutations.

Then, your algorithm becomes:

std::random_device rd;
std::mt19937 gen{ rd() };
std::uniform_int_distribution<> dist{ 1, 16 };

unique_sequence< unique_sequence<int> > perms;

while(perms.size() < 100)
{
    unique_sequence<int> perm;
    while(perm.size() < 16) perm.push_back(dist(gen));
    
    perms.push_back(std::move(perm));
}

And, here is complete implementation on coliru.

user_43585700

Simple and fast way to generate permutations is to use std::shuffle and std::next_permutation. Shuffle uses the efficient Fisher-Yates algorithm. Note that there are exactly 24 or 4! permutations in the {1,2,3,4} array.

#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <array>
#include <iostream>

template <typename T>
void print(std::vector<T>& v)  // print vector of arrays
{
    for (const auto& a : v)
    {
        for (auto x : a)
            std::cout << x << ' ';
        std::cout << '\n';
    }
    std::cout << '\n';
}

int main()
{
    std::array<int, 4> a4{ 1, 2, 3, 4 }; // use std::iota for longer sequences
    std::array<int, 16> a16{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
    std::vector<std::array<int, 4>> a4_all;
    a4_all.push_back(a4);
    for (int i = 1; i < 2*3*4; i++) // there's 2*3*4=24 permuations
    {
        std::next_permutation(a4.begin(), a4.end());
        a4_all.push_back(a4);
    }
    std::random_device rd;
    std::mt19937 g(rd());
    std::vector<std::array<int, 16>> vp100(100, a16);
    for (int i = 0; i < 100; i++)
        std::shuffle(vp100[i].begin(), vp100[i].end(), g); // shuffle is fastest
    print(a4_all);
    print(vp100);
}

Compiler Explorer

user_52821540
Related