Comparing permutation verbs:
perm
3 : 0
z=. i.1 0
for. i.y do. z=. ,/ (0 ,. 1 + z) {"2 1 \:"1 = i. 1 + {: $z end.
:
,/ ({~ perm@#)"1 x comb y
)
tap
A.&i.~ !
tap1
i.@! A. i.
timespacex 'perm 10'
0.125342 6.03984e8
timespacex 'tap 10'
0.845453 1.11569e9
timespacex 'tap1 10'
0.847798 1.11569e9
Dyadic use:
timespacex '5 perm 15'
0.0318871 2.00029e7
timespacex '5 tap 10'
|index error: tap
| 5 tap 10
timespacex '5 tap1 10'
|index error: tap1
| 5 tap1 10
So 'perm', the explicit recursive version of a permutation-generating verb,
is considerably more efficient, and it is dyadic. It also handles
permutation subsets.
Skip Cave
Cave Consulting LLC
On Mon, Mar 15, 2021 at 8:08 AM 'Mike Day' via Chat <[email protected]>
wrote:
> Sorry, I forgot to spell it out.
> tap achieves the same as perm, though I think perm is an explicit
> recursive or looping
> function.
>
> tap is probably one of Roger’s whizzbangs; tap is an acronym for
> something like Table all
> permutations.
>
> The version I happened to use yesterday is
> i.@! A. i.
> but I love the more compact
> A.&i.~!
>
> In either case, my expression involving tap could just as well be
> 1,. 2 + perm 7
> which generates 5040 permutations of 2,3,...8 and pretends 1 in “fixed”
> position.
>
> Cheers,
>
> Mike
>
> Sent from my iPad
>
> > On 15 Mar 2021, at 02:35, Skip Cave <[email protected]> wrote:
> >
> > Here is the J Programming thread about Rotational Duplicates:
> > http://jsoftware.com/pipermail/programming/2020-May/055839.html
> >
> > Mike Day - What is the "tap" verb in your equation?
> >
> > $s3=.+/"1[3,\"1|:n,2{.n=.|:1,.2+tap 7
> > 5040 8
> >
> >
> > Skip Cave
> > Cave Consulting LLC
> >
> >
> >> On Sun, Mar 14, 2021 at 8:01 PM Skip Cave <[email protected]>
> wrote:
> >>
> >> Mike,
> >> You are right. I forgot about rotational duplicates.
> >> I had a similar problem awhile back, and Roger showed us several ways to
> >> remove rotational duplicates.
> >> Here is one of Roger's verbs:
> >>
> >> rdr=.3 :'~.(y i."_1<./"1 y)|."_1 y' NB. Remove rotational duplicates.
> >>
> >> $n=.>:perm 8
> >>
> >> 40320 8
> >>
> >> $rdr n
> >>
> >> 5040 8
> >>
> >> So there are only 5,040 unique vertex permutations.
> >>
> >> Skip Cave
> >> Cave Consulting LLC
> >>
> >>
> >> On Sun, Mar 14, 2021 at 6:55 PM 'Mike Day' via Chat <[email protected]
> >
> >> wrote:
> >>
> >>> As these are supposed to be regular polygons, shouldn’t you identify
> >>> 123...8 with
> >>> 234...81 etc, in which case there are !7 rather than !8 different
> >>> octagons.
> >>>
> >>> Also, we only need consider the minimum triplet sum in each figure,
> >>> since, by definition, all other triplet sums in that octagon are
> greater
> >>> or equal.
> >>>
> >>> So:
> >>> $s3=.+/"1[3,\"1|:n,2{.n=.|:1,.2+tap 7
> >>> 5040 8
> >>>
> >>> +/m=.*./"1[11<"1 s3. NB. 8 times smaller because of equivalence under
> >>> rotation...
> >>> 40
> >>>
> >>> +/11<<./"1 s3. NB. same comparing minimum triplet-sums
> >>> 40
> >>>
> >>> It is fairly straightforward to develop a constructive function to
> >>> generate polygons with n
> >>> sides for which all k-tuplets of consecutive corners sum to more than
> >>> some value. It’s a lot slower than using perm or tap for octagons,
> but
> >>> would be competitive for somewhat larger polygons.
> >>>
> >>> Since +/>: i. 8 = 36, the average triplet sum is 13.5 = 108%3 , we
> know
> >>> that there is no
> >>> such octagon with all triplet sums exceeding 13.
> >>>
> >>> Mike
> >>>
> >>>
> >>> Sent from my iPad
> >>>
> >>>> On 14 Mar 2021, at 22:00, Skip Cave <[email protected]> wrote:
> >>>>
> >>>> I found this problem on Quora. I had fun solving it in J. Are there
> more
> >>>> efficient ways?
> >>>>
> >>>> The first 8 natural numbers (1 to 8) are positioned on the vertices of
> >>> an
> >>>> octagon. Is it possible to position the numbers such that the sum of
> >>> any 3
> >>>> adjacent vertices is greater than 11? Greater than 13?
> >>>>
> >>>> Using the J programming language, brute force approach:
> >>>>
> >>>> Wikipedia: "J (programming language)"
> >>>>
> >>>> J primitives: NuVoc - J Wiki <https://code.jsoftware.com/wiki/NuVoc>
> >>>>
> >>>> Generate all permutations of the integers 1–8, & store them in n.
> Count
> >>> the
> >>>> permutations & display the count:
> >>>>
> >>>> $n=.|:>:perm 8
> >>>>
> >>>> 8 40320
> >>>>
> >>>> So n contains the 40,320 possible permutations of the integers 1–8,
> >>>> representing all the possible permutations of the numbered vertices of
> >>> an
> >>>> octagon.
> >>>>
> >>>> Now sum consecutive sets of three integers from each set of 8 integers
> >>> with
> >>>> wraparound, which will create sets of 8 sums, and store the sums in
> s3.
> >>>> Count the sums & display the count:
> >>>>
> >>>> $s3=.+/"1[3,\"1|:n,2{.n
> >>>>
> >>>> 40320 8
> >>>>
> >>>> So s3 has 40,320 sets of 8 sums, where each set of 8 sums represents
> >>> the 8
> >>>> sums of 3 adjacent vertices on each unique octagon.
> >>>>
> >>>> Now mark all the octagons have all their 3 consecutive vertex sums
> >>> greater
> >>>> than 11, sum the marks, and list the sum:
> >>>>
> >>>> +/m=.*./"1[11<"1 s3
> >>>>
> >>>> 320
> >>>>
> >>>> So 320s of the 40,320 possible octagons have all their 3 consecutive
> >>> vertex
> >>>> sums greater than 11:
> >>>>
> >>>> Use the mark vector to extract & display the first & last few sets of
> >>>> octagon vertices whose 3 consecutive vertex sums are greater than 11:
> >>>>
> >>>> {m#|:n
> >>>>
> >>>> │1 4 7 2 5 6 3 8│1 4 7 2 6 5 3 8│1 5 6 2 4 7 3 8│1 5 6 2 7 3 4 8│1 5 6
> >>> 2 7
> >>>> 4 3 8│1 5 6 2 8 3 4 7│1 5 6 3 7 2 4 8│1 5 6 3 8 2 4 7│1 5 6 4 2 7 3
> 8│1
> >>> 5 6
> >>>> 4 7 2 3 8│….
> >>>>
> >>>> …..│8 3 5 6 2 7 4 1│8 3 6 4 2 7 5 1│8 3 6 5 1 7 4 2│8 3 6 5 2 7 4 1│8
> 3
> >>> 7 2
> >>>> 4 6 5 1│8 3 7 4 2 6 5 1│8 4 2 7 3 5 6 1│8 4 2 7 3 6 5 1│8 4 3 7 2 5 6
> >>> 1│8 4
> >>>> 3 7 2 6 5 1│
> >>>>
> >>>> How many octagons have all their 3 consecutive vertex sums greater
> than
> >>> 13?
> >>>>
> >>>> +/*./"1[13<"1 s3
> >>>>
> >>>> 0
> >>>>
> >>>> There are no octagons whose 3 consecutive vertex sums are all greater
> >>> than
> >>>> 13.
> >>>>
> >>>> How many octagons have all their 3 consecutive vertex sums greater
> than
> >>> 10?
> >>>>
> >>>> +/*./"1[10<"1 s3
> >>>>
> >>>> 3456
> >>>>
> >>>> So 3,456 octagons of the 40,320 possible octagons have all their 3
> >>>> consecutive vertex sums greater than 10.
> >>>>
> >>>> Skip Cave
> >>>> Cave Consulting LLC
> >>>> ----------------------------------------------------------------------
> >>>> 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
