Yes. We're talking about a previous thread though.
Just as A. provides a direct path to a permuted arrangement, permN and combN
provided a direct compressed path to permutations (that may include repeats)
and combinations. PermC is the function that calculates the total number of
possible permutations.
The functions that you modeled all generate a full list and then search it for
the answer. Takes a lot of space for sure. indexes store these
permutations/combinations in much less memory.
There's a couple of alternative ways to "walk through" alternative permutations:
1. random permutations and combinations can be done through A. For repeat
perms index from i.@# to sorted list. For combinations take k from n can be
randomly taken as k {. index of A. in i.@n
2. next function that takes as input a permutation or combination, and returns
the next one in order.
for permutations, this could be quick
(i.@# -: \:)\. 0 2 1 4 3
0 0 0 1 1
tells us the index to pivot is 2, the new value is the next highest elemenent
in positions 3 4, and the remaining values are ascended sorted remainder.
repeats are a bit tricker.
Still for "storing high scoring" permutations/combinations (part of a
search/optimization/game process), the index takes less space and can be stored
along other scalars (say the score).
These techniques also allow data storage as combination # (unique symbols),
frequency of each symbol, permutation number with same total storage space as
raw data, but the storage format allows indexing based on the presence of a
symbol (not limited to a single character code, but relies on a global app
dictionary), or its frequency minimum.
----- Original Message -----
From: Raul Miller <[email protected]>
To: Programming forum <[email protected]>
Sent: Tuesday, May 10, 2016 12:50 PM
Subject: Re: [Jprogramming] challenge: optimizing permutations with repeat
count
So, ok, let's review.
A. is "Anagram Index" but presumes that each position being permuted
is distinct or potentially distinct.
We can simulate it like along these lines:
A012=: /:~ ({~ (A.&i.~ !)@#) 0 1 2
A012 i. 2 0 1
4
A. 2 0 1
4
If we are to decide that we want to support repeated characters, we
get a slightly different formulation. We should be able to simulate
that like this:
A0011=: /:~ ~. ({~ (A.&i.~ !)@#) 0 0 1 1
A0011 i. 1 0 1 0
4
Now... it's true that A. has a few extensions beyond this.
One extension is that if we index off the end of the possibilities we
get an error instead of an unusable index.
We can simulate that like this:
A012 ([ i. i. { [) 2 0 1
4
A0011 ([ i. i. { [) 1 0 1 0
4
Another converts error cases into "valid index" cases. For A. we can
model that extension like this:
extend=: (-.~ , [) i.@>:@(>./)
A012 ([ i. i. { [) extend 2 0 1
But this extension relies on knowing that each index appears exactly
once in the permutation - so we have to give up this extension when
working with permutations with repeats.
So, let's take the above and turn them into testable models (not
efficient, but useful for discussion purposes):
all=: /:~@({~ (A.&i.~ !)@#)
extend=: (-.~ , [) i.@>:@(>./)
index=: [ i. i. { [
Adot=: (all index ]) extend
Aana=: ~.@all index ]
But, anyways, this is how I understand the specification as you have
stated it, so far.
And, when I do a few tests, it it looks like what you have is
consistent with this.
Does my point of view make sense to you?
If not, let me know where I went wrong?
If so... sorry I was so slow.
Thanks,
--
Raul
On Tue, May 10, 2016 at 8:33 AM, 'Pascal Jasmin' via Programming
<[email protected]> wrote:
> They're the same if the constraint is equal rather than upto a frequency
> count/distribution.
>
>
>
>
> ----- Original Message -----
> From: Raul Miller <[email protected]>
> To: Programming forum <[email protected]>
> Sent: Tuesday, May 10, 2016 2:48 AM
> Subject: Re: [Jprogramming] challenge: optimizing permutations with repeat
> count
>
> Those are two different concepts, as I understand them:
>
> "Anagrams with repetition":
> AABB
> ABAB
> ABBA
> BAAB
>
> Constrained by a frequency count for each digit:
> ABB
> ABBA
> BAA
> BAB
>
> FYI,
>
> --
> Raul
>
>
> On Tue, May 10, 2016 at 2:12 AM, 'Pascal Jasmin' via Programming
> <[email protected]> wrote:
>> Cool, but not quite the same. A permutation (in the sense I'm looking for)
>> is constrained by a frequency count for each digit: Anagrams with
>> repetition.
>>
>>
>>
>> ----- Original Message -----
>> From: Raul Miller <[email protected]>
>> To: Programming forum <[email protected]>
>> Sent: Tuesday, May 10, 2016 12:11 AM
>> Subject: Re: [Jprogramming] challenge: optimizing permutations with repeat
>> count
>>
>> Here's another approach for permutations with repetitions in J.
>>
>> If we characterize a permutation with repetitions as belonging to a
>> sequence with a specific length a, and a maximum value b, and having
>> an index value y, we can a verb for the argument pattern (a,b) Ap y
>> like this:
>>
>> Ap=: #/@[ #: ]
>>
>> Example use:
>>
>> 10 60 Ap ?5#60^10x
>> 34 56 50 9 15 28 34 11 40 43
>> 32 9 50 41 37 25 41 18 36 47
>> 30 27 17 58 19 40 41 2 31 25
>> 23 18 33 58 24 20 32 38 38 0
>> 29 16 32 9 59 46 36 15 10 40
>>
>> Thanks,
>>
>> --
>> Raul
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
