1. Re[2]: How to make routine like this
- Posted by aku at inbox.as
Dec 13, 2001
Thanks!
But are there better solutions, without checking duplicate
digits in in the left? Because I need it to be very fast.
_____________________________________________________________________
e> <aku at inbox.as> wrote:
>> input output (can be any length)
>> (parameter)
>>
>> 1 {0,1,2,3,4}
>> 2 {0,1,2,3,5}
>> 3 {0,1,2,3,6}
>> .
>> .
>> .
>> x-2 {9,8,7,5,4}
>> x-1 {9,8,7,5,6}
>> x {9,8,7,6,5}
>>
>>
>> How to make such routine?
>> And how to determine x?
>>
>> Thanks very much!
e> Reading from left to right in the sequence, you have a choice of 10 digits
e> in the first position, nine in the second (since you're not repeating digits
e> and you've used one already in the first column), eight in the third, seven
e> in the fourth, and six in the fifth. Thats 10x9x8x7x6 possible combinations,
e> or 30240.
e> It's similar to work it out for any length. Notice it wouldn't be possible
e> to have a length more than 10 - you don't have enough symbols.
e> Here's one way to do it (untested). It won't work if your data columns
e> require numbers outside 0-9 though...
e> --------
e> sequence numbers, format
e> integer len, i, invalid, skip
e> len = 5 -- set length here
e> format = sprintf("%%0%dd", len)
e> skip = 0
e> for j = 1 to len-1 do
e> skip = 10 * skip + j
e> end for
e> i = skip
e> while i < power(10, len+1) - skip do
e> invalid = 1
e> while invalid do
e> numbers = sprintf(format,i) - '0'
e> invalid = 0
e> for j = 2 to 5 do
e> if find(numbers[j-1], numbers[j..5]) then
e> invalid = 1
e> i += 1
e> exit
e> end if
e> end for
e> end while
e> ? numbers
e> i += 1
e> end while
e> --------
e> There are ways to adapt this to accept any range of data items, or even any
e> *set* of data items. These are left as exercises to the reader. Hint: don't
e> use sprintf(). :)
e> HTH,
e> Carl
2. Re: Re[2]: How to make routine like this
<aku at inbox.as> wrote:
> Thanks!
>
> But are there better solutions, without checking duplicate
> digits in in the left? Because I need it to be very fast.
Warning! Untested:
function get_permutation(sequence symbolSet, integer len, integer
permutation)
sequence remaining, out
integer max, pos, divisor, element
integer setLength
setLength = length(symbolSet)
-- Calculate total mumber of permutations and generate an index list
max = 1
remaining = repeat(0, setLength)
for i = 1 to setLength
remaining[i] = i
if i >= len then
max *= i
end if
end for
-- Actions based on permutation number
if permutation = 0 then
-- Handy for calculating exactly how many permutations there are
return max
elsif not (1 <= permutation and permutation <= max) then
-- There are no permutations outside the 1..max range
return -1
end if
-- Generate the output using some cunning math(s)
out = {}
pos = permutation
divisor = max
for i = 1 to len do
divisor /= len - i + 1
element = floor(pos / divisor)
pos -= divisor * element
element += 1
out &= symbolSet[remaining[element]]
remaining =
remaining[1..element-1] &
remaining[element+1..length(remaining)]
end for
return out
end function
sequence digits
digits = {0,1,2,3,4,5,6,7,8,9}
? get_permutation( digits, 5, 0 )
-- prints the number of permutations of 'digits' with 5 elements.
-- (should be 30240)
? get_permutation( digits, 5, 50000 )
-- prints -1 -- there is no 50000th 5-digit permutation of 'digits'.
? get_permutation( digits, 5, 29050 )
-- prints the 29050th 5-digit permutation of 'digits'
To generate all possible combinations like last time:
for i = 1 to get_permutation( digits, 5, 0 ) do
? get_permutation( digits, 5, i )
end for
HTH,
Carl
