1 /* Boost.MultiIndex example of use of rearrange facilities.
2 *
3 * Copyright 2003-2020 Joaquin M Lopez Munoz.
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE_1_0.txt or copy at
6 * http://www.boost.org/LICENSE_1_0.txt)
7 *
8 * See http://www.boost.org/libs/multi_index for library home page.
9 */
10
11 #if !defined(NDEBUG)
12 #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
13 #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
14 #endif
15
16 #include <boost/config.hpp>
17 #include <boost/multi_index_container.hpp>
18 #include <boost/multi_index/random_access_index.hpp>
19 #include <boost/random/binomial_distribution.hpp>
20 #include <boost/random/uniform_real.hpp>
21 #include <boost/random/mersenne_twister.hpp>
22 #include <algorithm>
23 #include <iostream>
24 #include <iterator>
25 #include <vector>
26
27 #if !defined(BOOST_NO_CXX11_HDR_RANDOM)
28 #include <random>
29 #endif
30
31 using boost::multi_index_container;
32 using namespace boost::multi_index;
33
34 /* We model a card deck with a random access array containing
35 * card numbers (from 0 to 51), supplemented with an additional
36 * index which retains the start ordering.
37 */
38
39 class deck
40 {
41 BOOST_STATIC_CONSTANT(std::size_t,num_cards=52);
42
43 typedef multi_index_container<
44 int,
45 indexed_by<
46 random_access<>, /* base index */
47 random_access<> /* "start" index */
48 >
49 > container_type;
50 container_type cont;
51
52 public:
deck()53 deck()
54 {
55 cont.reserve(num_cards);
56 get<1>(cont).reserve(num_cards);
57 for(std::size_t i=0;i<num_cards;++i)cont.push_back(i);
58 }
59
60 typedef container_type::iterator iterator;
61 typedef container_type::size_type size_type;
62
begin() const63 iterator begin()const{return cont.begin();}
end() const64 iterator end()const{return cont.end();}
size() const65 size_type size()const{return cont.size();}
66
67 template<typename InputIterator>
rearrange(InputIterator it)68 void rearrange(InputIterator it)
69 {
70 cont.rearrange(it);
71 }
72
reset()73 void reset()
74 {
75 /* simply rearrange the base index like the start index */
76
77 cont.rearrange(get<1>(cont).begin());
78 }
79
position(int i) const80 std::size_t position(int i)const
81 {
82 /* The position of a card in the deck is calculated by locating
83 * the card through the start index (which is ordered), projecting
84 * to the base index and diffing with the begin position.
85 * Resulting complexity: constant.
86 */
87
88 return project<0>(cont,get<1>(cont).begin()+i)-cont.begin();
89 }
90
rising_sequences() const91 std::size_t rising_sequences()const
92 {
93 /* Iterate through all cards and increment the sequence count
94 * when the current position is left to the previous.
95 * Resulting complexity: O(n), n=num_cards.
96 */
97
98 std::size_t s=1;
99 std::size_t last_pos=0;
100
101 for(std::size_t i=0;i<num_cards;++i){
102 std::size_t pos=position(i);
103 if(pos<last_pos)++s;
104 last_pos=pos;
105 }
106
107 return s;
108 }
109 };
110
111 /* A vector of reference_wrappers to deck elements can be used
112 * as a view to the deck container.
113 * We use a special implicit_reference_wrapper having implicit
114 * ctor from its base type, as this simplifies the use of generic
115 * techniques on the resulting data structures.
116 */
117
118 template<typename T>
119 class implicit_reference_wrapper:public boost::reference_wrapper<T>
120 {
121 private:
122 typedef boost::reference_wrapper<T> super;
123 public:
implicit_reference_wrapper(T & t)124 implicit_reference_wrapper(T& t):super(t){}
125 };
126
127 typedef std::vector<implicit_reference_wrapper<const int> > deck_view;
128
129 /* Riffle shuffle is modeled like this: A cut is selected in the deck
130 * following a binomial distribution. Then, cards are randomly selected
131 * from one packet or the other with probability proportional to
132 * packet size.
133 */
134
135 template<typename RandomAccessIterator,typename OutputIterator>
riffle_shuffle(RandomAccessIterator first,RandomAccessIterator last,OutputIterator out)136 void riffle_shuffle(
137 RandomAccessIterator first,RandomAccessIterator last,
138 OutputIterator out)
139 {
140 static boost::mt19937 rnd_gen;
141
142 typedef typename std::iterator_traits<
143 RandomAccessIterator>::difference_type difference_type;
144 typedef boost::binomial_distribution<
145 difference_type> rnd_cut_select_type;
146 typedef boost::uniform_real<> rnd_deck_select_type;
147
148 rnd_cut_select_type cut_select(last-first);
149 RandomAccessIterator middle=first+cut_select(rnd_gen);
150 difference_type s0=middle-first;
151 difference_type s1=last-middle;
152 rnd_deck_select_type deck_select;
153
154 while(s0!=0&&s1!=0){
155 if(deck_select(rnd_gen)<(double)s0/(s0+s1)){
156 *out++=*first++;
157 --s0;
158 }
159 else{
160 *out++=*middle++;
161 --s1;
162 }
163 }
164 std::copy(first,first+s0,out);
165 std::copy(middle,middle+s1,out);
166 }
167
168 struct riffle_shuffler
169 {
operator ()riffle_shuffler170 void operator()(deck& d)const
171 {
172 dv.clear();
173 dv.reserve(d.size());
174 riffle_shuffle(
175 d.begin(),d.end(),std::back_inserter(dv)); /* do the shuffling */
176 d.rearrange(dv.begin()); /* apply to the deck */
177 }
178
179 private:
180 mutable deck_view dv;
181 };
182
183 /* A truly random shuffle (up to stdlib implementation quality) using
184 * std::shuffle.
185 */
186
187 struct random_shuffler
188 {
operator ()random_shuffler189 void operator()(deck& d)
190 {
191 dv.clear();
192 dv.reserve(d.size());
193 std::copy(d.begin(),d.end(),std::back_inserter(dv));
194 shuffle_view();
195 d.rearrange(dv.begin()); /* apply to the deck */
196 }
197
198 private:
199 deck_view dv;
200
201 #if !defined(BOOST_NO_CXX11_HDR_RANDOM)
202 std::mt19937 e;
203
shuffle_viewrandom_shuffler204 void shuffle_view()
205 {
206 std::shuffle(dv.begin(),dv.end(),e);
207 }
208 #else
209 /* for pre-C++11 compilers we use std::random_shuffle */
210
shuffle_viewrandom_shuffler211 void shuffle_view()
212 {
213 std::random_shuffle(dv.begin(),dv.end());
214 }
215 #endif
216 };
217
218 /* Repeat a given shuffling algorithm repeats_num times
219 * and obtain the resulting rising sequences number. Average
220 * for tests_num trials.
221 */
222
223 template<typename Shuffler>
shuffle_test(unsigned int repeats_num,unsigned int tests_num BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE (Shuffler))224 double shuffle_test(
225 unsigned int repeats_num,unsigned int tests_num
226 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Shuffler))
227 {
228 deck d;
229 Shuffler sh;
230 unsigned long total=0;
231
232 for(unsigned int n=0;n<tests_num;++n){
233 for(unsigned m=0;m<repeats_num;++m)sh(d);
234 total+=d.rising_sequences();
235 d.reset();
236 }
237
238 return (double)total/tests_num;
239 }
240
main()241 int main()
242 {
243 unsigned rifs_num=0;
244 unsigned tests_num=0;
245
246 std::cout<<"number of riffle shuffles (vg 5):";
247 std::cin>>rifs_num;
248 std::cout<<"number of tests (vg 1000):";
249 std::cin>>tests_num;
250
251 std::cout<<"shuffling..."<<std::endl;
252
253 std::cout<<"riffle shuffling\n"
254 " avg number of rising sequences: "
255 <<shuffle_test<riffle_shuffler>(rifs_num,tests_num)
256 <<std::endl;
257
258 std::cout<<"random shuffling\n"
259 " avg number of rising sequences: "
260 <<shuffle_test<random_shuffler>(1,tests_num)
261 <<std::endl;
262
263 return 0;
264 }
265