Permutations by Interchange

[A Ask]

https://academic.oup.com/comjnl/article/6/3/293/360213?login=false was published in 1963.  (the full PDF is available as a download).

The recursive implementation of  this algorithm in APL is bewildering not least because most implementations in other languages  resort to showing the result in a text file rather than as a result of the function.

Some examples:

      PermuteByInterchange 'APL'
APL
PAL
LAP
ALP
PLA
LPA
      PermuteByInterchange 'APL' 'Is' 'Easy'
 APL  Is   Easy
 Is   APL  Easy
 Easy APL  Is
 APL  Easy Is
 Is   Easy APL
 Easy Is   APL
      ⍴PermuteByInterchange 'APL' 'Is' 'Easy'
6 3
      PermuteByInterchange 3 14 15 16
  3 14 15 16
 14  3 15 16
 15  3 14 16
  3 15 14 16
 14 15  3 16
 15 14  3 16
 16 14  3 15
 14 16  3 15
  3 16 14 15
 16  3 14 15
 14  3 16 15
  3 14 16 15
  3 15 16 14
 15  3 16 14
 16  3 15 14
  3 16 15 14
 15 16  3 14
 16 15  3 14
 16 15 14  3
 15 16 14  3
 14 16 15  3
 16 14 15  3
 15 14 16  3
 14 15 16  3
      ⍴PermuteByInterchange 3 14 15 16
24 4
      ⍝ 4 options, therefore the number of permutations is
      !4
24
      ⍝ That is the first dimension of PermuteByInterchange 3 14 15 16 

Your solution?

[Davin Church]

This article describes a scalar, iterative solution, of course, but I wouldn't write an APL function that way. Using APL it doesn't sound terribly difficult to write a recursive array algorithm to do the same thing and ignore the scalar flow they describe. Do you need this for some purpose? And if so, is it necessary to do it "by interchanges"?

[Ajay Askoolum]

I started looking at https://en.wikipedia.org/wiki/Heap%27s_algorithm#:~:text=Heap's%20algorithm%20generates%20all%20possible,2%20elements%20are%20not%20disturbed.; in particular the recursive version. Writing the recursive solution in APL provided me new insights into how the APL signature arguments (i.e. LHA and RHA) are localised. There are two formidable challenges (with the scalar flow approach):

1. Getting the recursion to work in APL. The for loop  for i := 0; i < k-1; i += 1 do does not work in APL.

2. Getting APL to accumulate the results and return it on completion. The solution at the link dumps each result with output(A)  (to a file or console)

The same challenges arise with recursive Fibonacci; here too the next result depends on the previous one.

My current objective is to see if I can automate the mapping out cross function/variable dependencies in a workspace (and recursive functions depend on themselves).

[Davin Church]

Hmmm...

I don't know why you think that control loop would not work - are you having a specific problem with it?

Accumulating results should be perfectly doable in APL. I have my own permutation function for APL - it's recursive and terribly simple but doesn't return results in that order. It's also not suitable for returning very large arrays.

Returning results was one of the things the article's author was trying to avoid, because they wanted to be able to work with lists larger than would fit in memory, so they did it that way on purpose.

I seem to remember an article once talking about determining the nth term of Fibonacci without going through the whole process, but it was really complicated and I'm probably not remembering the right thing anyway. Of course, the nth/mth term of a binomial expansion is trivial.

If all you want is function cross-referencing, though, I've got tools to do that, too.

[Ajay Askoolum]

> If all you want is function cross-referencing, though, I've got tools to do that, too.

That part is nearly (optimisation & tidying  is pending as well as coping with workspaces with no functions or no variables or both) done. Unzip the attached & open wrkspace.html which has links to the remaining pages. 

These html pages relate to an out of the box workspace: it would be interesting to compare your cross-reference for the same workspace.

[Ajay Askoolum]

I need to clarify this: in the Variable XRef Lines.HTML file you will see oriental characters at the beginning of the last 2 lines. This is the result of an obnoxious  Windows 11 feature .

In Control Panel, Region | Administrative | Change System Locale there is a Beta: Use  Unicode UTF-8 for worldwide language support check box that Windows Update has enabled by default and without warning. With that, Windows uses code page 65001 instead of 850. I forgot to switch to code page 850 before generating the html files.

[Ajay Askoolum]

> I don't know why you think that control loop would not work - are you having a specific problem with it?

It is not the loop itself - easily translated by hard-coding []io to 0.

The APL function doe not return correct values in the same order as C# does and APL returns wrong values. I've verified the C# results (which are correct); here's the code:

       static void Permute(int[] A, int n)
        {
            if (n == 1)
            {
                //printArray(A);
            }
            else
            {
                for (int i = 0; i < n-1 ; i++)
                {
                    Permute(A, n - 1);
                    if (n % 2 == 0)
                    {
                        A = Swap(A, i, n - 1);
                    }
                    else
                    {
                        A = Swap(A, 0, n - 1);
                    }
                    printArray(A);
                    Ar.Add(A);
                }
                Permute(A, n - 1);
            }
        }

On Wednesday, 8 March 2023 at 23:04:22 UTC Davin Church wrote:

[Davin Church]

I'm busy on another project tonight, but don't worry about mine if you've already got yours working. Mine's more of a utility rather than a fancy report - it does all the analysis and just returns results.

[Davin Church]

Ok, without looking at it in depth, I'd guess you've just got a coding bug somewhere. I had the same sort of problem when I was trying to write an MD5 replacement for ancient APLs.