Prev: now open all blocked site with our proxy
Next: ANN: Seed7 Release 2010-01-03
From: Mok-Kong Shen on 3 Jan 2010 06:46

Permutations of n different objects can be ordered and thus mapped to
numbers. There are good algorithms for doing the conversions. See

http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms

If there are only two kinds of objects (say, black and white), with n
even and n/2 objects of each kind, are there good algorithms of doing
the same?

Thanks,

M. K. Shen

From: Patricia Shanahan on 3 Jan 2010 12:23
Mok-Kong Shen wrote:
>
> Permutations of n different objects can be ordered and thus mapped to
> numbers. There are good algorithms for doing the conversions. See
>
> http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms
>
>
> If there are only two kinds of objects (say, black and white), with n
> even and n/2 objects of each kind, are there good algorithms of doing
> the same?

This is equivalent to the problem of specifying a set of n/2 unique
numbers each in the range from 1 through n. Regard the selected set as
the index values for the black elements. Any index not in the set gets a
white element.

There are n choices for the first number, n-1 choices for the second
one, ..., 1+n/2 choices for the last of the n/2 selected numbers.

Patricia
From: Mok-Kong Shen on 3 Jan 2010 13:20
Patricia Shanahan wrote:
> Mok-Kong Shen wrote:
>>
>> Permutations of n different objects can be ordered and thus mapped to
>> numbers. There are good algorithms for doing the conversions. See
>>
>> http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms
>>
>>
>> If there are only two kinds of objects (say, black and white), with n
>> even and n/2 objects of each kind, are there good algorithms of doing
>> the same?
>
> This is equivalent to the problem of specifying a set of n/2 unique
> numbers each in the range from 1 through n. Regard the selected set as
> the index values for the black elements. Any index not in the set gets a
> white element.
>
> There are n choices for the first number, n-1 choices for the second
> one, ..., 1+n/2 choices for the last of the n/2 selected numbers.

Sorry for my poor knowledge, I don't yet quite understand you. For
exalmple, with n=3 (and 1/0 for black/white), how does the entire
ordering look like (giving a part of it is sufficient) and how does
one compute, e.g. the index for 0 1 1 0 0 1?

Thanks in advance.

M. K. Shen
From: Patricia Shanahan on 3 Jan 2010 13:23
Mok-Kong Shen wrote:
> Patricia Shanahan wrote:
>> Mok-Kong Shen wrote:
>>>
>>> Permutations of n different objects can be ordered and thus mapped to
>>> numbers. There are good algorithms for doing the conversions. See
>>>
>>> http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms
>>>
>>>
>>>
>>> If there are only two kinds of objects (say, black and white), with n
>>> even and n/2 objects of each kind, are there good algorithms of doing
>>> the same?
>>
>> This is equivalent to the problem of specifying a set of n/2 unique
>> numbers each in the range from 1 through n. Regard the selected set as
>> the index values for the black elements. Any index not in the set gets a
>> white element.
>>
>> There are n choices for the first number, n-1 choices for the second
>> one, ..., 1+n/2 choices for the last of the n/2 selected numbers.
>
> Sorry for my poor knowledge, I don't yet quite understand you. For
> exalmple, with n=3 (and 1/0 for black/white), how does the entire
> ordering look like (giving a part of it is sufficient) and how does
> one compute, e.g. the index for 0 1 1 0 0 1?

Sorry, I should have been clearer. I'm not giving a complete solution,
just an idea for an approach that might work, when combined with ideas
from the link you posted.

Patricia
From: Mok-Kong Shen on 3 Jan 2010 16:52
Patricia Shanahan wrote:
> Mok-Kong Shen wrote:
>> Patricia Shanahan wrote:
>>> Mok-Kong Shen wrote:
>>>>
>>>> Permutations of n different objects can be ordered and thus mapped to
>>>> numbers. There are good algorithms for doing the conversions. See
>>>>
>>>> http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms
>>>>
>>>>
>>>>
>>>> If there are only two kinds of objects (say, black and white), with n
>>>> even and n/2 objects of each kind, are there good algorithms of doing
>>>> the same?
>>>
>>> This is equivalent to the problem of specifying a set of n/2 unique
>>> numbers each in the range from 1 through n. Regard the selected set as
>>> the index values for the black elements. Any index not in the set gets a
>>> white element.
>>>
>>> There are n choices for the first number, n-1 choices for the second
>>> one, ..., 1+n/2 choices for the last of the n/2 selected numbers.
>>
>> Sorry for my poor knowledge, I don't yet quite understand you. For
>> exalmple, with n=3 (and 1/0 for black/white), how does the entire
>> ordering look like (giving a part of it is sufficient) and how does
>> one compute, e.g. the index for 0 1 1 0 0 1?
>
> Sorry, I should have been clearer. I'm not giving a complete solution,
> just an idea for an approach that might work, when combined with ideas
> from the link you posted.

I am clueless and should appreciate it, if someone could kindly give
me a bit more help.

M. K. Shen
 |  Next  |  Last
Pages: 1 2 3
Prev: now open all blocked site with our proxy
Next: ANN: Seed7 Release 2010-01-03