Re: Solution needed..urgent!!

From:

Kai-Uwe Bux <jkherciueh@gmx.net>

Newsgroups:

comp.lang.c++

Date:

Fri, 07 Nov 2008 00:17:18 -0500

Message-ID:

<4913ce6a$0$17066$6e1ede2f@read.cnntp.org>

to restore context:

You are given a deck containing n cards. While holding the deck:

1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck
in your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is a
round.
4. Pick up the deck from the table and repeat steps 1-3 until the deck
is in the original order.

Write a program to determine how many rounds it will take to put a
deck back into the original order.

yog.mittal@gmail.com wrote:

I will really appreciate if anybody could please post the solution ?

I shall ignore the requirement that STL not be used. I hope that my solution
therefore will not qualify for the homework (also, some time has passed).
Also, I shall not use the algorithm outlined in the description of the
problem but use an entirely different idea that will give the same output.

Also: I will assume that the compiler supports long long (you really want
some arbitrary length integral type). The program will silently wrap around
and not report the overflow. I attach some values that I found, which
illustrate that point. At n=280, 2^32 will not suffice and at n=1004, the
result is beyond 2^64. (These numbers also illustrate why I will not
determine the order of the permutation by counting: it would take forever.)

#include <cassert>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>
#include <iostream>

// #include <kubux/integer>

// typedef kubux::integer arithmetic_type;
typedef unsigned long long arithmetic_type;

typedef std::vector< unsigned long > permutation;

permutation id ( unsigned long n ) {
  permutation result;
  result.reserve( n );
  for ( unsigned long i = 0; i < n; ++i ) {
    result.push_back( i );
  }
  return ( result );
}

void shuffle ( permutation & perm ) {
  permutation result;
  result.reserve( perm.size() );
  while ( ! perm.empty() ) {
    result.push_back( perm.front() );
    perm.erase( perm.begin() );
    std::rotate( perm.begin(), perm.begin() + 1, perm.end() );
  }
  std::swap( result, perm );
}

arithmetic_type gcd ( arithmetic_type a, arithmetic_type b ) {
  if ( b < a ) {
    std::swap( a, b );
  }
  while ( a != 0 ) {
    arithmetic_type dummy( b % a );
    b = a;
    a = dummy;
  }
  return( b );
}

arithmetic_type lcm ( arithmetic_type a, arithmetic_type b ) {
  arithmetic_type quot = b / gcd(a,b);
  return ( a * ( b / gcd(a,b) ) );
}

arithmetic_type order ( permutation const & p ) {
  arithmetic_type l ( 1 );
  std::set< unsigned long > still_free;
  std::copy( p.begin(), p.end(),
             std::inserter( still_free, still_free.end() ) );
  while ( ! still_free.empty() ) {
    unsigned long index = *(still_free.begin());
    unsigned long where = index;
    arithmetic_type length = arithmetic_type();
    do {
      ++ length;
      where = p[where];
      still_free.erase( where );
    } while ( where != index );
    l = lcm( l, length );
  }
  return ( l );
}

arithmetic_type number ( unsigned long n ) {
  permutation p ( id( n ) );
  shuffle( p );
  return ( order( p ) );
}

int main ( void ) {
  for ( unsigned long n = 1; ; ++n ) {
    std::cout << n << " --> " << number(n) << '\n';
  }
}

/*
  Some values:
  1 --> 1
  3 --> 2
  5 --> 3
  6 --> 5
  7 --> 6
  10 --> 9
  12 --> 28
  18 --> 70
  23 --> 210
  35 --> 308
  38 --> 990
  44 --> 2618
  58 --> 13300
  67 --> 27720
  68 --> 203490
  83 --> 360360
  111 --> 1021020
  112 --> 1511640
  113 --> 6230070
  162 --> 59254020
  185 --> 1376845470
  230 --> 2153331180
  280 --> 56270739378
  315 --> 591118103520
  338 --> 2328245689770
  441 --> 7600186994400
  554 --> 247651817843430
  689 --> 3993173946822060
  839 --> 16415300091350160
  907 --> 24858416865744000
  944 --> 27303154083485280
  947 --> 150103870204688400
  949 --> 4073014663549605312
  1004 --> 889351355342914944480
  1307 --> 1423178772983737169400
  1649 --> 709044136174739580415200
  1705 --> 1384460057373814306578000
  1799 --> 17843737077119301787398960
  1934 --> 26473022063487459901268520
  1948 --> 412108799554731513698624160
  2591 --> 10132942664275877164628800800
  2606 --> 492252055940052814523176659600
  3011 --> 4061133619046911989389682594720
  3368 --> 28987127583211271154658957499520
  3472 --> 28786869259134681128048175521961000
  4037 --> 13968231274398330387225456621929156160
  4451 --> 44613968405036781772417636768076148600
  4743 --> 47127723619287268204539720673201387200
  4924 --> 1015809212163473864903934664023523839570
  6387 --> 91321559704961673892472654357633041307427900
  7772 --> 9027755125844404863192942627813586968870041001600
  8921 --> 46137862364188321895572339367552812592575522848000
  9749 --> 1514900913329751772087279522915115470030101944229120
*/

Best

Kai-Uwe Bux