Car Rally

Manipulate[ran=SeedRandom[ranint];With[{rpermut=Randompermut[n]},With[{vec=Combinatorica`ToInversionVector[rpermut]},
Column[{"","Initial order:",Range[n],"","List of overtakings:",vec,"",If[sh,Column[{"Final order:",rpermut}]],"",If[sha,Column[{"Algorithm's steps:",Column[Reverse[fromInversion2[vec]]]}]]}]
]],{{n,10},Range[5,20]},{ranint,RandomInteger[{1,2347}],ControlType->None},{{sh,False,"show solution"},{True,False}},{{sha,False,"show steps of algorithm"},{True,False}},Button["new puzzle",ranint=RandomInteger[{1,34567}];sh=False;sha=False,ImageSize->130],ContentSize->{520,430},SynchronousInitialization->False,Initialization:>(Quiet@Get["Combinatorica`"];RandomKsublist[set_,k_]:=Module[{sub={},rest=set,new},
Do[new=rest[[RandomInteger[{1,Length[rest]}]]];sub=AppendTo[sub,new];rest=Complement[rest,{new}],{k}];sub];
Randompermut[k_]:=RandomKsublist[Range[k],k];fromInversion2[vec_]:=Module[{i,n=Length[vec]+1,p},p=Table[{},{n}];p[[n]]={n};Do[p[[i]]=Insert[p[[i+1]],i,vec[[i]]+1],{i,n-1,1,-1}];p]
)]

At a certain stage of a car rally n participants  (labeled by first n positive integers) started in sequence of their labels.  We are given n-1 numbers. The number at position i means how many participants, that started after i-th have overtaken him or her. There are only n-1 numbers because no one has started after n-th. What was the order at the end of stage?

The algorithm is as follows. We begin with the initial order and last participant. Suppose we have already ordered sequence {i+1, i+2,..., k}. Now we insert i  the number of places to the right as is given by the number of overtakes.

The mentioned sequence of  n-1 numbers is called inversion vector of final order (permutation).

S. Permmaraju, S. Skiena, Computational Discrete Mathematics, Cambridge University Press, 2003, pp. 69-71.

Contributed by: Izidor Hafner