HP49-HP50 Lists of combination

[Gil]

Suppose that I have 7 variables or objects , x1... x7.

Suppose that I fix x1 in function of 4 other variables,
say x1=a2x2+ a3x3+ a4x4 + a5x5.

How could I get all the groups of 4 variables
(6!/(4!*2!) = 5*6/2 = 15 possibilities, for example in a big list like, not including x1:

{{x2, x3, x4, x5}
{x2, x3, x4, x6}
{x2, x3, x4, x7}

x2, x3, x5, x6}
x2, x3, x5, x7}
x2, x3, x6, x7}

x2, x4, x5, x6}
x2, x4, x5, x7}
x2, x4, x6, x7}

x2, x5, x6, x7}

x3, x4, x5, x6}
x3, x4, x5, x7}
x3, x4, x6, x7}

x3, x5, x6, x7}

x4, x5, x6, x7}}

entering two arguments, in this example n=7 and m=4 in HP50G?

Unfortunately I get stuck to that problem. I think that I should use a recursive program, as n and m are variable parameters.

Thanks in advance for your help.

Gil

[Thomas Klemm]

This works for the HP-48GX:

Code:

«
  « → m s 
    « IF m 1 ==
      THEN s 1 « 1 →LIST » DOLIST
      ELSE IF m s SIZE ==
        THEN s 1 →LIST
        ELSE m 1 - s TAIL ←C EVAL
          1 « s HEAD SWAP + » DOLIST
          m s TAIL ←C EVAL +
        END
      END
    »
  » → ←C
  « ←C EVAL
  »
»

It is mostly a verbatim translation of the following Python program:

Code:

def comb(m, s):
    if m == 1: return [[x] for x in s]
    if m == len(s): return [s]
    return [s[:1] + a for a in comb(m-1, s[1:])] + comb(m, s[1:])

The use of a compiled local variable is inspired by Gerald's program.

Example

Assuming that the program is saved as comb:

4 ENTER
{ x2 x3 x4 x5 x6 x7 }
comb

{
{ x2 x3 x4 x5 }
{ x2 x3 x4 x6 }
{ x2 x3 x4 x7 }
{ x2 x3 x5 x6 }
{ x2 x3 x5 x7 }
{ x2 x3 x6 x7 }
{ x2 x4 x5 x6 }
{ x2 x4 x5 x7 }
{ x2 x4 x6 x7 }
{ x2 x5 x6 x7 }
{ x3 x4 x5 x6 }
{ x3 x4 x5 x7 }
{ x3 x4 x6 x7 }
{ x3 x5 x6 x7 }
{ x4 x5 x6 x7 }
}

I'm sure that there's room for improvements.

References

• Generate Combinations on Rosetta Code
• (49G) OEIS A035327
  

[DavidM]

The ListExt library has a DOCOMB function that would be very useful here.

The arguments for DOCOMB are fairly straightforward:

SL3: { the list of n items to combine }
SL2: <the number of choices for each combination [1..n]>
SL1: « an action to perform for each combination »

The "action to perform" can be a null program (« ») if you just want the list elements returned as combinations in a larger list.

So in this case, you would put the following on the stack:
{ x2 x3 x4 x5 x6 x7 }
4
« »

...then execute DOCOMB. The output using the above arguments is:
{
{ x2 x3 x4 x5 }
{ x2 x3 x4 x6 }
{ x2 x3 x4 x7 }
{ x2 x3 x5 x6 }
{ x2 x3 x5 x7 }
{ x2 x3 x6 x7 }
{ x2 x4 x5 x6 }
{ x2 x4 x5 x7 }
{ x2 x4 x6 x7 }
{ x2 x5 x6 x7 }
{ x3 x4 x5 x6 }
{ x3 x4 x5 x7 }
{ x3 x4 x6 x7 }
{ x3 x5 x6 x7 }
{ x4 x5 x6 x7 }
}

There's also a DOPERM that works in a similar fashion for permutations.

[Gil]

Thanks for your answers and references.

It works fine (of course!), but I still will have to study carefully that Cery compact program, in particular also the special use he ehthe special use of <—C.

Regards,
Gil

[Thomas Klemm]

From the HP 48G Series Advanced User’s Reference Manual p. 1-15:

Quote:Compiled Local Variables
Global variables use up memory, and local variables can’t be used outside of the program they were created in.
Compiled local variables bridge the gap between these two variable types.
To programs, compiled local variables look like global variables, but to the calculator they act like local variables.
This means you can create a compiled local variable in a local variable structure, use it in any other program that is called within that structure, and when the program finishes, the variable is gone.

There's nothing magical about using ←C: it just contains the recursive program.
But it allows to use itself inside the program, even though the assignment was made outside.

We could have used a global variable comb instead and used that.
The benefit would be that it could be easily invoked without using EVAL.
However, if someone decided to use a different global variable name, the program had to be adjusted.
Using a compiled local variable avoids this.

---

Using the debugger and stepping through the code with a small example can help to understand the code.
Also, I recommend reading the referenced blog post.
You can also try to implement the other two solutions.

[Gil]

In my last program I did use a lot of such <—xi special variable, that I put right at the main program and used back and again on the different subroutines.

After your explanation relative to the name inside the rescursive program, I see the purpose of using here your <—C variable as a full program.

Very nicely thought.

All very compact, as in Python.

Regards and thanks for sharing your deep knowledge.

Gil

[Thomas Klemm]

Perhaps using a CASE instead of nested IF statements makes reading easier:

Code:

«
  « → m s 
    « CASE
        m 1 ==
        THEN s 1 « 1 →LIST » DOLIST
      END
        m s SIZE ==
        THEN s 1 →LIST
      END
        m 1 - s TAIL ←C EVAL
        1 « s HEAD SWAP + » DOLIST
        m s TAIL ←C EVAL +
      END
    »
  » → ←C
  « ←C EVAL
  »
»

[Gil]

Not necessarily.

The reference you gave should make already things clear, as well your explanation relative to the program itself by means of <—C, that I used to have at the very beginning of a program (like for local variable)

The smart part is the basic idea given in Python.
It would certainly have never occurr to me to procede such nicely.
As for the DOLIST command, I have to get used to that most powerful tool.

Congratulations for this compact translation from Python to HP50G.

There are indeed very bright people around the world, above all concerning HP universe.

Regards and again thanks for sharing.

With your program, I should finish the extreme directions calculation for my SIMPLEX program.

Gil

[Thomas Klemm]

(12-19-2022 03:35 PM)Gil Wrote:  It would certainly have never occur to me to proceed such nicely.

That's certainly true. It follows the recursive relationship of Pascal's Triangle:

\(
\begin{align}
{s \choose m} = {s-1 \choose m-1} + {s-1 \choose m}
\end{align}
\)

[Werner]

My version of DOCOMB. Contrary to the ListExt lib version, intermediate results are not automatically wrapped up in a list, and so the calling sequence for your problem is rather

3: list
2: 4.
1: \<< 4. \->LIST \>>

Code:

@ DOCOMB 265.5 bytes #CC35h
\<<
  ROT 0
  \-> ob L DoC
  \<<
    DEPTH DEPTH ROLLD
    L SIZE
    {}
    { 3 PICK 1 -
      \-> t n
      \<<
        IF n
        THEN FOR s n s 1 - L s GET 1 \->LIST t + DoC EVAL NEXT 
        ELSE FOR s L s GET t LIST\-> DROP ob EVAL NEXT
        END
      \>>
    } DUP 'DoC' STO EVAL
    DEPTH DEPTH ROLL -
    IF DUP 0 > THEN \->LIST ELSE DROP END
  \>>
\>>