Random pair maker

[Knocturne]

I need to make a program that takes a set of values and pairs them up at random, without repeats. Is there any way to use the random_shuffle() algorithm to do so? I'm unsure how to approach the problem.

[LB]

With both lists in hand, shuffle one list and just pair things up as you simultaneously iterate both lists ;)

[Knocturne]

It's all in a single list, though. A list of names (they can be represented by integers if it's simpler). I need the program to read that list, shuffle them and pair the values up at random.

[Manga]

how many items in each list? I actually have code that could solve this problem for you.

But if you want to do it yourself, then here is the approach I took.

I played with rand until I had it generate the number of possibilities I wanted. Lets say 10. Then I looped it. So that it would keep producing a random draw but then check first to see if that one was picked already. If so, draw again. If that possibility was not yet picked. Then it stuck. This would create a random list of 10 items that never duplicate. Now repeat with list 2. Once you have your 2 lists, stick 'em together.

[Knocturne]

That's just about exactly what I want to do. So, I should use rand() to split the single list into two, and then shuffle those amongst themselves. Is there any way to make it more... selective? It rather defeats the purpose of a random generator, but for example, say I wanted to prevent "a" to be paired with "b", but any other pairing for "a" is acceptable.

[JLBorges]

A set of values can't be shuffled; the values (which form the key) are always maintained in sorted order.

We can copy the values (or if these are expensive to copy, pointers or references to them) to a vector, shuffle the vector, and form pairs out of the shuffled values/pointers/references.

#include <set>
#include <vector>
#include <functional>
#include <algorithm>

// take a set of values and pairs them up at random, without repeats.
template < typename T >
std::vector< std::pair<T,T> > make_unique_pairs( const std::set<T>& set )
{
    std::vector< std::pair<T,T> > result ;

    // make a vector of references to elements in the set
    std::vector< std::reference_wrapper< const T > > seq( set.begin(), set.end() ) ;

    // make a random permutation of the references
    std::random_shuffle( std::begin(seq), std::end(seq) ) ;

    // make pairs and place them into the result
    for( std::size_t i = 0 ; i < seq.size() - 1 ; i += 2 )
        result.emplace_back( seq[i], seq[i+1] ) ;

    return result ;
}

#include <cstdlib>
#include <ctime>
#include <iostream>

int main()
{
    std::srand( std::time(nullptr) ) ;

    const std::set<int> values { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } ;

    for( auto pair : make_unique_pairs(values) )
        std::cout << pair.first << ',' << pair.second << '\n' ;
}

http://ideone.com/jWimrx

[Manga]

What do you mean JLBorges? A random number can be used to represent anything. And besides your code lookes too professional. I can't read it yet.

Although if yours works, it is a lot shorter than my code.

[JLBorges]

> It's all in a single list, though.
> A list of names (they can be represented by integers if it's simpler).
> I need the program to read that list, shuffle them and pair the values up at random.

Hadn't read this when I made my post; I was under the impression that it was a std::set<> of unique values.

Use a vector of strings (instead of a list); for shuffling, we need random access iterators. Shuffle the vector, and then pair up elemts at position (0,1) (2,3) (4,5) etc.

#include <cstdlib>
#include <ctime>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main()
{
    std::srand( std::time(nullptr) ) ;

    std::vector<std::string> seq { "Knocturne", "LB", "Manga", "JLBorges", "abc",
                                      "def", "ghi", "jkl", "mno", "pqr", "stu" } ;

    std::random_shuffle( std::begin(seq), std::end(seq) ) ;

    for( std::size_t i = 0 ; i < seq.size() - 1 ; i += 2 )
        std::cout << "pair " << seq[i] << " with " << seq[i+1] << '\n' ;
}

http://ideone.com/uB13Qn

[Duthomhas]

Holy crap! I didn't know the STL could do that so simply. I had written this earlier, but could only post it now... [edit] Oh, wait, nevermind. I just didn't know about emplace, but all you did was just put it in a loop...[/edit]

You'll want to use some rather exotic features in Boost to do it, called range adaptors.

Here's an example:

#include <chrono>
#include <iostream>
#include <iterator>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

#include <boost/range/adaptor/sliced.hpp>
#include <boost/range/adaptor/strided.hpp>
#include <boost/range/algorithm/transform.hpp>

using namespace std;
using namespace boost;

int main()
  {
  // Get number of pairs
  cout << "How many pairs? ";
  size_t n;
  cin >> n;
  
  // Convert to size of list
  n *= 2;
  
  // Create list of unique numbers (1..n)
  vector <int> xs( n, 1 );
  partial_sum( xs.begin(), xs.end(), xs.begin() );

  // Randomize it
  unsigned seed = chrono::system_clock::now().time_since_epoch().count();
  shuffle( xs.begin(), xs.end(), default_random_engine( seed ) );
  
  // Pair them up
  vector <pair <int, int> > ps;
  transform( 
    xs                                    | adaptors::strided( 2 ), 
    xs | adaptors::sliced( 1, xs.size() ) | adaptors::strided( 2 ), 
    back_inserter( ps ), 
    [] ( int a, int b ) { return make_pair( a, b ); }
    );

  // Display the results
  for (auto p: ps) cout << "(" << p.first << ", " << p.second << ")\n";
  
  return 0;
  }

Lines 36-41 are what you are interested in.
Notice that this isn't the std::transform() algorithm, but the boost:: one.
Line 37 gets every other element of xs starting with the first, and line 38 gets every other element starting with the second. Make sure xs has an even number of elements!

Hope this helps.

[sakry]

"L B" That worked for me u_u