Fixing Unordered combinations custom block

[brooks.ogborn]

Hello Snappers!

Brooks (25M) here. I'm pretty good at math, but have always been a bit intimidated by coding so I've only just started using Snap last month I've been coming up with Snap coding projects to do for fun... I've gotten stuck on my most recent experiment.

The block gives the cross product of the lists, and it works as I understand it just fine, giving the result:

I want a slightly different block, that looks like this:
and that gives the following:

Essentially, I'm taking combinations of the first n numbers, no repeats, and only up to reordering of the selected numbers. Here's a slightly bigger example to get the point across:
The block should give the output:

At least, that's what I'm trying to do. Unordered combinations. Once I have this block I can use its array to map over other lists and get their unordered combinations.

There are probably many ways to do this easily, but the way I made up mimicked what you might do with paper and pencil. For unordered combinations first 6 numbers, choosing 3 at a time, I write as reference 1, 2, 3, 4, 5, 6, and then start taking combinations in this order:
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
.... and so on.
Essentially, I call the bolded numbers Anchors. List the Anchors, then if there's room, move the rightmost anchor right one, and if there isn't room, move the next anchor right one and slide the others back.

Anyways, I'm having trouble implementing this (probably due to my lack of Snap familiarity, or coding familiarity in general.) Here's something really close:

So when running the unordered combinations block, (with inputs 6 and 3) it reports just an empty list. Here, I'm nesting the script "Anchor Runner" a number of times equal to the __-tuples I'm taking. Before entering the next nesting level, I append a list containing the anchor (the bold number) to the Updator List. If I'm at the deepest level, I also append the Updator List to the end of the Running List. It's really close to working... in the visible stepping the innermost nested layer works as intended, but when we go back out a layer to move the second to last anchor, the Running List was input earlier as blank, so the running list reverts to blank.

I have found a way around this, which is to scrap the input "Running List" and just make a Global Variable which gets appended by the Updator list. (This is how I got the list photos above). But I don't like this solution because it feel like a work-around, and I want this block to work without any global variables.

Again, I'm sure there are many ways to accomplish my goal (all of which I'm happy to see), but I'm particularly interested in fixing the code with the least amount of overhaul as possible, so as to expand my learning in this particular area.

Any suggestions?

Brooks

P.S. From just one list or set of objects, I want to be able to take all possible n-tuples with or without replacement, with or without order.

P.S. I've tried looking at maybe making the Running List an UpVar, that didn't seem to work, and also at making it an Unevaluated Input, that didn't seem to work either, but maybe I just don't fully comprehend how these work.

[bh]

Hi, Brooks, welcome to Snap!.

Just checking, does "25M" mean you're 25 years old? Because if you're a kid you shouldn't use your real name online, including as your Snap! user ID.

Okay, so, since you ask for the minimal change to your code, the thing that jumps out at me (not necessarily the last bug) is that the input variables of a procedure (the ones declared as part of the header) are local to each procedure call; each time you call Anchor Runner you are making a new PreviousAnchor, a new Maximum, etc. The old one is still around, in the old procedure call. This allows you to define recursive functions, e.g.,

Pascal(n,r) = Pascal(n-1, r-1) + Pascal(n-1, r)

which wouldn't work if there were a single variable N and a single variable R. (I'm leaving out the base cases, the ones at the left and right edges, because they're not relevant to the point I'm trying to make with this example, but of course you'd have to deal with them to write a working procedure.)

So, when you say REPORT(RUNNING LIST) at the end of your main procedure, you are reporting that procedure's variable, which is still an empty list. And you have the same problem with the recursive calls to ANCHOR RUNNER.

So, how do you fix this? The minimal-change way depends on the fact that if an input to a procedure is a list, even though the input variable in the called procedure is separate from the same-name variable in the caller, the two variables initially point to the same list. If you change the variable in the called procedure using SET, as you do for RunningList, then the two variables no longer point to the same list. But if you use the list mutation commands ADD, INSERT, DELETE, or REPLACE, such as the DELETE command near the end of your helper procedure, then you are changing the list itself, not assigning a different value to the variable in the called procedure, and the caller does see that change. So instead of

SET RUNNINGLIST TO (APPEND...)

you could say

ADD UPDATORLIST TO RUNNINGLIST

and the caller would see that change. (See this FAQ entry for more details.) That's not the best possible solution, since it works only for lists, but it's only list variables that you SET.

---

But since you're good at math, you should have more faith in the math, and in particular more faith in functions. The way I'd look at this problem is to say "all the combinations can be divided into the ones that include the first number and the ones that don't include the first number." So I'd define UNORDERED COMBINATIONS as

IF (TUPLES = 0)
  REPORT (LIST (LIST))     see note 2 below
ELSE
  REPORT (APPEND 
           (MAP ((MINIMUM) IN FRONT OF ()) (UNORDERED ...)))   see note 1 below
           (UNORDERED ...))

Note 1: This isn't something I'd expect you to know about already. The function should take MINIMUM and MAXIMUM as inputs, not just MAXIMUM. The two recursive calls, although not quite the same, will use MINIMUM+1 as the minimum number. The first input to APPEND has to be "the combinations that include MINIMUM" and the way you compute that is to start by computing the combinations of length TUPLES-1 from MINIMUM+1 to MAXIMUM, then stick MINIMUM in front of each of those combinations.

So, how do you compute some function of each item of a list? You use MAP, whose inputs are a function (that's what the gray ring means) and a list. In the function, in this case IN FRONT OF, you leave one of the input slots empty, and that's where each item of the second (list) input will be used.

I'm leaving out a lot, but that's because you want to learn by doing. Ask more questions if you have more when you actually write the code.

Note 2: When defining a function recursively, you need a base case. So, in Pascal's triangle, you have to say that if R=0 or R=N, the value is 1. In this case, the base case is tuples of size zero. Such a tuple is empty. But the set of all such tuples isn't empty; it contains one tuple, the empty one. That's why the base case reports (LIST (LIST)) and not just (LIST). I'm telling you this because nobody ever figures it out themself the first time. :~)

By the way, "unordered combinations" is redundant. The ordered ones are called "permutations."

---

A few little points about Snap! coding:

You have four calls to SCRIPT VARIABLES at the top of your procedure. You could replace them with a single call, by using that little black right arrowhead at the end of the block to give it more input slots. Each time you click the arrowhead you get one more script variable. (Protip: If you hold down the Shift key while clicking the arrowhead, you get three more input slots at once!)

Calling APPEND with just one input reports that input unchanged. So in the SET RUNNINGLIST instruction you can just say
(APPEND (RUNNING LIST) (LIST (UPDATOR LIST))).

But if you are willing to keep Updator List in reverse order, you don't need APPEND at all; you can just say
(UPDATOR LIST) IN FRONT OF (RUNNING LIST)

(Note, if you make either of the changes I suggested, these tips about APPEND become irrelevant because you're not going to use it. But they're still good to learn.)

Instead of MINIMUM and MAXIMUM, you could give the procedure a list as input to get combinations of its items. So then you'd use (NUMBERS FROM 1 TO _) as the list, to get the same results you're getting now, but you could use arbitrary values and skip mapping over the result to get the values you really want.

When making pictures of procedures to post in the forum (or for any purpose), instead of making a screenshot, right-click on the header in the block editor and choose "Script pic" from the menu. Besides being easier, this creates a picture that includes the actual Snap! code as metadata, so you can drag the picture into Snap! and it'll load the code into that Snap! workspace. (Drag it into the Scripts tab, not into the Costumes tab; the latter will load the picture as just a picture.)

[ego-lay_atman-bay]

@bh

When making pictures of procedures to post in the forum (or for any purpose), instead of making a screenshot, right-click on the header in the block editor and choose "Script pic" from the menu.

They were already using that, I know because I imported an image into snap and it loaded the block.

[brooks.ogborn]

Hey bh!

Thanks for your help! Yes I'm 25 years old. "M" mean male. I actually have a Math/Stats Education degree, and I'm taking some CS courses to get a CS Teaching Endorsement, and my first class is based on the Berkley BJC labs. I finished all of the coursework in a few weeks and I'm just trying some more experiments in Snap!.

TL:DR I just now used your comments to fix my bug, and I feel like I understand my bug and how to fix it in the future. Your detailed answer in the FAQ question about I copied a list to another variable, and then when I change the copy, it changes the original too! also helped me understand more fully what you were explaining. I also browsed the Snap! manual pages 48 and 49.

I thought that I understood the list structure mechanics before, but this bug helped me understand them even more. I remember early on in the BJC labs that we had to use the Append block, otherwise when we alter the result then the original list changes also. Essentially, I overused SET list block, mostly because I was thinking I had to use APPEND for everything. Really, I should use append only when I want to make a new object, but use the list mutation commands like ADD when I want to change an existing list. The commands ADD, INSERT, DELETE, REPLACE are used to change an existing list (the mutation commands, which are the imperative style).

Other blocks like APPEND, ALL BUT FIRST OF, IN FRONT OF, make new lists that have no effect on lists that were pointed to earlier by another variable. These are the functional style blocks for lists.

Maybe I didn't explain those very well, but I'm getting there.

Additionally, I'm not so sure I understand what you are saying when you say "Calling APPEND with just one input reports that input unchanged. So in the SET RUNNINGLIST instruction you can just say (APPEND (RUNNING LIST) (LIST (UPDATOR LIST)))". Without the APPEND around UPDATOR LIST, then when I later DELETE last OF (UPDATOR LIST), then the running list content changes also, which is not what I intended. But it's fixed now anyway, so I'm not too worried about that part.

Here's my new script, with only the changes necessary to fix it, no other changes:

I still had to use one Append block when adding the Updator List to the Running list, because otherwise the Running list contents would be deleted later on... like I was saying before.

Here's my first attempt at creating a functional version of the same block:
Gets stuck in an infinite loop.

This one was close to working, but would get stuck in an infinite loop because the pink UNORDERED... block would keep increasing the minimum past the maximum infinitely.

Here is my second attempt at creating a functional version:
Works as intended.

This one works as intended. I now have two if checks near the start, so that if the procedure is ran with a minimum greater than the maximum, then an empty list is reported and no further nesting is done. (Is it still called nesting with the functional style? This reminds me of fractal structures.) I have to be careful with the order of the if statements... in the pink MAP block, for the tuples in which the last number is equal to the Max, that number still needs to be put IN FRONT OF the empty list, and the empty list needs to come from list reported by the red UNORDERED... block that follows, calling with min+1>max.

Carefully reading page 70 of the Snap! manual also helped me a lot with this. It probably took me about 40 minutes of solid thinking to understand the script there, but I love learning and this is just great!

Anyways, that's a lot to think about and it was really fun solving this puzzle in two very different ways! I appreciate the encouragement and advice, bh!

I know that "unordered combinations" are called "combinations", but seeing as there is a primitive block called "combinations" already, I figured I would be specific. I remember learning about permutations and combinations way back in 9th grade. Good times! I might start on a Permutations block... I can already do that imperatively using my custom predicate <Does (LIST) repeat?>... but I wonder if I can do it functionally? I'm not sure, this is going to take some practice.

I saved both custom "Unordered Combinations" blocks. I went a little further and created another block called "Combinations of %List picking %n at a time". Actually, I tried to create two blocks, one Imperative style and one Functional style. The idea is the same, but now you can use a list of anything, not just integers from Min to Max. These new blocks rely on the tuple generator blocks, but they could be combined with a bit of effort. Here are my two combination blocks:

Imperative:

Functional:

Having tested all four of these blocks, the Functional blocks are much quicker to run than the imperative blocks. This is confirming of the ideas you set forth in the FAQ question I mentioned earlier, that the Functional style often runs in linear time, but the Imperative style often runs in quadratic time.

I'm nearly wrapped up with this project... but I'd love any last comments you or another person might have about my attempts at the functional style of list generating.

Thanks!

Mr. Ogborn

P.S. The FAQ and Manual are great!

[bh]

@ego-lay_atman-bay

They were already using that, I know because I imported an image into snap and it loaded the block.

Huh. Not for me. Weird.

[bh]

@brooks.ogborn

and my first class is based on the Berkley BJC labs.

Cool!

@brooks.ogborn

I'm not so sure I understand what you are saying when you say "Calling APPEND with just one input reports that input unchanged. So in the SET RUNNINGLIST instruction you can just say (APPEND (RUNNING LIST) (LIST (UPDATOR LIST)))". Without the APPEND around UPDATOR LIST, then when I later DELETE last OF (UPDATOR LIST), then the running list content changes also, which is not what I intended.

Oh! Right you are. I was thinking that the value reported by one-input APPEND is the input. (It never occurs to me to write list code iteratively, except for special cases such as making a debugging log with ADD _ TO LOG.)

ITEM (1) OF (NUMBERS FROM MIN TO MAX)

This is just MIN. :~)

But yeah, good point about the second base case. I'm embarrassed that I didn't think of that. (And that I posted the code without testing it, but I'll never learn.)

@brooks.ogborn

I know that "unordered combinations" are called "combinations", but seeing as there is a primitive block called "combinations" already, I figured I would be specific.

Oh yeah huh. I generally just use "combs."

Recursive permutations is a little less elegant than recursive combinations, but it's quite doable.

@brooks.ogborn

This is confirming of the ideas you set forth in the FAQ question I mentioned earlier, that the Functional style often runs in linear time, but the Imperative style often runs in quadratic time.

I have to admit that the lists have to be quite long before the order of growth outweighs the constant factor in runtime. It's pedagogically important for people teaching data structures (CS 2).

@brooks.ogborn

I went a little further and created another block called "Combinations of %List picking %n at a time"

You should write it without using numbers at all! That way you'll learn more about list operations. And also, that way you'll refrain from teaching your students about index numbers. :~)

@brooks.ogborn

P.S. The FAQ and Manual are great!

Thanks!

[qw23]

Great to see your progress!
In my experience, recursive algorithms are really relatively easy to write and understand (i.e. compared to alternative solutions) once you get the principle.

---

If you're interested, here's an addition (I hope it's not too advanced )
There's just one issue with recursion: algorithms with branches (2+) tend to recalculate the same results over and over and over again (and again and again ...). If you try to make a seriously big list (like 9-tuples from a list A-Z: over 3 million items) the recursive processing is going to take way too much time.

You could then resort to memoization to speed up the process. See my explanation / demonstration below.

This is how long it takes (on my platform, in milliseconds; thx to @dardoro for the DURATION block!) to generate all combinations (not permutations) of 5 items from a list with letters A through Z (65,780 items):

I had my home-crafted fully-automatic functions memoizer (follow the above link) create a memoized version of the combinations generator:

Now this is how long (or actually: short) it takes for the memoized version to generate the same result:

If the number of items in each tuple increases, the processing time of the original generator (which is similar to your recursive version) explodes - I think it's in the order of (n!), approximately. By contrast, the memoized version will generate up to 9-tuples of the same list within reasonable time:

Since all results are kept, if you ask the memoized version of the generator to do the same thing again, all it has to do is look up the previous result.

Better not increase the tupleness (tupility?) beyond 9 (with a list of 26 items), or Snap! will crash because of memory overflow.

[d4s_over_dt4]

@qw23

the DURATION block

(in the limit case,the duration block itsself takes about 2000ns due to the loop jump)

[qw23]

For most practical purposes the execution time of the duration block is not a significant factor (if it is, there's always a way to circumvent it). Besides, it is included in each of the cases that are being compared.

[d4s_over_dt4]

I am advertising my own block where I stuffed together in that rocket simulator project in like a minute
IMHO I should be accurate(2 microseconds is enough for light to travel 600 meters)
(ps:"2000ns" is accurate to the hundredth digit on 1000000 times average,and even with that level of accuracy,after multiple tests,most of them went on "2001ns")

[qw23]

So, you made a more accurate timer block - is that what you're saying? Will you share the code?

[brooks.ogborn]

Got it!

[bh]

@brooks.ogborn

Got it!

Yay! See how elegant that is?

[brooks.ogborn]

Here's a functional implementation of Permutations:

It uses a custom block "%List without %item", which I hope is self explanatory. It was just miles easier to read the code by making this block separate:

[d4s_over_dt4]

dragging the pic to the editor works on my side
snap tries to stuff the data into the comment section(s) in the image
you can think that snap gets your block(pun not intended) and changes the spin/# of neutrons of the atom core so that another snap can get out your data without doing computer vision/ocr or something

[qw23]

Thx, copying worked - though generally I feel that ideas are best shared by (also) ”printing” the relevant code within a forum post.

Back to your DURATION OF: it’s a (useful, I think) enhancement of @dardoro ’s, adding the element of a series of runs, and calculating the average run time.

I presume you won’t mind me sharing your code for others to learn from / use / be inspired by:

[bh]

If the time is accurate only to the millisecond, it's misleading to label it in nanoseconds (even if the result after averaging isn't an integer).

[d4s_over_dt4]

Yeah,I put the script pic there for sharing the code.You think that there are people who don't know how to drag script pics and post the definition,which conveys the same information.

[d4s_over_dt4]

Hmm?
We can prove that the most probable time(the maximum of the PDF) is the limit of the average.
Did you want to say that we should give the whole PDF?