1. Re[4]: How to make routine like this
- Posted by aku at inbox.as
Dec 14, 2001
I think this is wrong...
I get 151200 for ? get_permutation( digits, 5, 0 )
but I can't repair the problem ( I don't understand. )
Can you correct that? Thanks!
e> Warning! Untested:
e> function get_permutation(sequence symbolSet, integer len, integer
e> permutation)
e> sequence remaining, out
e> integer max, pos, divisor, element
e> integer setLength
e> setLength = length(symbolSet)
e> -- Calculate total mumber of permutations and generate an index list
e> max = 1
e> remaining = repeat(0, setLength)
e> for i = 1 to setLength
e> remaining[i] = i
e> if i >= len then
e> max *= i
e> end if
e> end for
e> -- Actions based on permutation number
e> if permutation = 0 then
e> -- Handy for calculating exactly how many permutations there are
e> return max
e> elsif not (1 <= permutation and permutation <= max) then
e> -- There are no permutations outside the 1..max range
e> return -1
e> end if
e> -- Generate the output using some cunning math(s)
e> out = {}
e> pos = permutation
e> divisor = max
e> for i = 1 to len do
e> divisor /= len - i + 1
e> element = floor(pos / divisor)
e> pos -= divisor * element
e> element += 1
e> out &= symbolSet[remaining[element]]
e> remaining =
e> remaining[1..element-1] &
e> remaining[element+1..length(remaining)]
e> end for
e> return out
e> end function
e> sequence digits
e> digits = {0,1,2,3,4,5,6,7,8,9}
e> ? get_permutation( digits, 5, 0 )
e> -- prints the number of permutations of 'digits' with 5 elements.
e> -- (should be 30240)
e> ? get_permutation( digits, 5, 50000 )
e> -- prints -1 -- there is no 50000th 5-digit permutation of 'digits'.
e> ? get_permutation( digits, 5, 29050 )
e> -- prints the 29050th 5-digit permutation of 'digits'
e> To generate all possible combinations like last time:
e> for i = 1 to get_permutation( digits, 5, 0 ) do
e> ? get_permutation( digits, 5, i )
e> end for
e> HTH,
e> Carl
2. Re: Re[4]: How to make routine like this
- Posted by rforno at tutopia.com
Dec 14, 2001
Aku:
I sent to the list another routine, that was tested and is very fast. You
might not have noticed it, so I am including it next now:
function var (sequence set, integer size, integer which)
integer c, len, a
if size <= 0 then
return {}
elsif size = 1 then
return {set[which]}
end if
len = length(set)
c = 1
for i = len - size + 1 to len - 1 do
c *= i
end for
a = floor((which - 1) / c)
which -= a * c
a += 1
return set[a] & var(set[1..a - 1] & set[a + 1..len], size - 1, which)
end function
for i = 1 to 60 do
? var({1, 2, 3, 4, 5}, 3, i)
end for
----- Original Message -----
From: <aku at inbox.as>
To: "EUforum" <EUforum at topica.com>
Sent: Friday, December 14, 2001 11:12 AM
Subject: Re[4]: How to make routine like this
>
>
> I think this is wrong...
>
> I get 151200 for ? get_permutation( digits, 5, 0 )
>
> but I can't repair the problem ( I don't understand. )
>
> Can you correct that? Thanks!
>
> e> Warning! Untested:
>
> e> function get_permutation(sequence symbolSet, integer len, integer
> e> permutation)
> e> sequence remaining, out
> e> integer max, pos, divisor, element
> e> integer setLength
>
> e> setLength = length(symbolSet)
>
> e> -- Calculate total mumber of permutations and generate an index
list
> e> max = 1
> e> remaining = repeat(0, setLength)
> e> for i = 1 to setLength
> e> remaining[i] = i
> e> if i >= len then
> e> max *= i
> e> end if
> e> end for
>
> e> -- Actions based on permutation number
> e> if permutation = 0 then
> e> -- Handy for calculating exactly how many permutations there
are
> e> return max
> e> elsif not (1 <= permutation and permutation <= max) then
> e> -- There are no permutations outside the 1..max range
> e> return -1
> e> end if
>
> e> -- Generate the output using some cunning math(s)
> e> out = {}
> e> pos = permutation
> e> divisor = max
>
> e> for i = 1 to len do
> e> divisor /= len - i + 1
> e> element = floor(pos / divisor)
> e> pos -= divisor * element
> e> element += 1
> e> out &= symbolSet[remaining[element]]
> e> remaining =
> e> remaining[1..element-1] &
> e> remaining[element+1..length(remaining)]
> e> end for
> e> return out
> e> end function
>
> e> sequence digits
> e> digits = {0,1,2,3,4,5,6,7,8,9}
>
> e> ? get_permutation( digits, 5, 0 )
> e> -- prints the number of permutations of 'digits' with 5 elements.
> e> -- (should be 30240)
>
> e> ? get_permutation( digits, 5, 50000 )
> e> -- prints -1 -- there is no 50000th 5-digit permutation of 'digits'.
>
> e> ? get_permutation( digits, 5, 29050 )
> e> -- prints the 29050th 5-digit permutation of 'digits'
>
> e> To generate all possible combinations like last time:
>
> e> for i = 1 to get_permutation( digits, 5, 0 ) do
> e> ? get_permutation( digits, 5, i )
> e> end for
>
> e> HTH,
> e> Carl
>
>
>
>
3. Re: Re[4]: How to make routine like this
- Posted by rforno at tutopia.com
Dec 14, 2001
Aku: The following routine is tested.
function var (sequence set, integer size, integer which)
integer c, len, a
if size <= 0 then
return {}
elsif size = 1 then
return {set[which]}
end if
len = length(set)
c = 1
for i = len - size + 1 to len - 1 do
c *= i
end for
a = floor((which - 1) / c)
which -= a * c
a += 1
if a > len or a <= 0 then
return - 1
end if
return set[a] & var(set[1..a - 1] & set[a + 1..len], size - 1, which)
end function
for i = 1 to 100 do
? var({1, 2, 3, 4, 5}, 3, i)
end for
? var({1, 2, 3, 4, 5}, 3, 0)
----- Original Message -----
From: <aku at inbox.as>
To: "EUforum" <EUforum at topica.com>
Sent: Friday, December 14, 2001 11:12 AM
Subject: Re[4]: How to make routine like this
>
>
> I think this is wrong...
>
> I get 151200 for ? get_permutation( digits, 5, 0 )
>
> but I can't repair the problem ( I don't understand. )
>
> Can you correct that? Thanks!
>
> e> Warning! Untested:
>
> e> function get_permutation(sequence symbolSet, integer len, integer
> e> permutation)
> e> sequence remaining, out
> e> integer max, pos, divisor, element
> e> integer setLength
>
> e> setLength = length(symbolSet)
>
> e> -- Calculate total mumber of permutations and generate an index
list
> e> max = 1
> e> remaining = repeat(0, setLength)
> e> for i = 1 to setLength
> e> remaining[i] = i
> e> if i >= len then
> e> max *= i
> e> end if
> e> end for
>
> e> -- Actions based on permutation number
> e> if permutation = 0 then
> e> -- Handy for calculating exactly how many permutations there
are
> e> return max
> e> elsif not (1 <= permutation and permutation <= max) then
> e> -- There are no permutations outside the 1..max range
> e> return -1
> e> end if
>
> e> -- Generate the output using some cunning math(s)
> e> out = {}
> e> pos = permutation
> e> divisor = max
>
> e> for i = 1 to len do
> e> divisor /= len - i + 1
> e> element = floor(pos / divisor)
> e> pos -= divisor * element
> e> element += 1
> e> out &= symbolSet[remaining[element]]
> e> remaining =
> e> remaining[1..element-1] &
> e> remaining[element+1..length(remaining)]
> e> end for
> e> return out
> e> end function
>
> e> sequence digits
> e> digits = {0,1,2,3,4,5,6,7,8,9}
>
> e> ? get_permutation( digits, 5, 0 )
> e> -- prints the number of permutations of 'digits' with 5 elements.
> e> -- (should be 30240)
>
> e> ? get_permutation( digits, 5, 50000 )
> e> -- prints -1 -- there is no 50000th 5-digit permutation of 'digits'.
>
> e> ? get_permutation( digits, 5, 29050 )
> e> -- prints the 29050th 5-digit permutation of 'digits'
>
> e> To generate all possible combinations like last time:
>
> e> for i = 1 to get_permutation( digits, 5, 0 ) do
> e> ? get_permutation( digits, 5, i )
> e> end for
>
> e> HTH,
> e> Carl
>
>
>
>
4. Re: Re[4]: How to make routine like this
- Posted by rforno at tutopia.com
Dec 16, 2001
John:
There is no problem. The difference crops up because you are using puts()
instead of ?. puts() prints the ASCII value instead of the numeric value.
The result, in case the number of the permutation (I think that in this case
it is called variation, but it was long ago when I left my statistics
books...) is out of range, is -1. But if you use puts(), -1 prints as
ASCII(255), which is what is called a "substitute blank" and, in fact,
prints as a blank. 255 comes from the binary representation of -1, which is
11111111111...etc . puts() takes the 8 lower bits to show the ASCII value
(please look at the Euphoria manual). If in the function you substitute -1
by '*', you will see an asterisk as the output.
To make it more technical, the function returns a sequence with the correct
permutation when the "which" parameter is in the right range, and an atom
otherwise. Being L the length of the original sequence, and T the length of
the intended result, the range is 1 to L * (L - 1) * ... * (L - T + 1) or
factorial(L) / factorial(L - T).
Out of curiosity: are you living in Portugal for work or just for pleasure?
Regards.
----- Original Message -----
From: "John McAdam" <johnmcadam at clix.pt>
To: "EUforum" <EUforum at topica.com>
Sent: Wednesday, December 12, 2001 6:02 PM
Subject: RE: Re[4]: How to make routine like this
>
> If the loop is too long (more than 100) it prints empty lines.
> How do you know there are only 100 combinations?
> I am using this only very slightly modified code,
> replacing numbers with letters and increasing the
> loop size to 125.
>
>
> function var (sequence set, integer size, integer which)
> integer c, len, a
>
> if size <= 0 then
> return {}
> elsif size = 1 then
> return {set[which]}
> end if
>
> len = length(set)
> c = 1
> for i = len - size + 1 to len - 1 do
> c *= i
> end for
>
> a = floor((which - 1) / c)
> which -= a * c
> a += 1
> if a > len or a <= 0 then
> return - 1
> end if
> return set[a] & var(set[1..a - 1] & set[a + 1..len], size - 1, which)
> end function
>
> for i = 1 to 125 do --125 is too many!
> puts(1,var({'A','B','C','D','E'}, 5, i)&"\n")
> end for
> ? var({1, 2, 3, 4, 5}, 3, 0)
>
>
>
>
