LibreOffice Calc: generating a list of permutations of a set?

English
#1

Hi. I have a set of 7 strings – I’ll call them A,B,C,D,E,F,G. I want them in random order – e.g. F, C, E, A, G, B, D. Normally, this would be no problem – I’d just put these 7 strings in a column, then put random numbers in a second column, and sort on that second column.

The problem is that I want to do this 100 times, with each random shuffling of these seven strings on its own row. So, the rows might look like this:

Row 1: F | C | E | A | G | B | D
Row 2: C | G | A | F | D | B | E
Row 3: D | F | B | G | C | A | E
Row 4: (another permutation)
and so on down to Row 100.

The permutations should be random – which means it’s OK if there are duplicate rows.

The approach above would still work; but apart from having to swap columns for rows, there’s also having to do it 100 times, which seems crazy.

Is there a straightforward way to take a set of N items, and generate M random permutations of those N items, each on its own row?

I did a quick google and search of the forum here; but the responses I found generally referred back to the simple random arrangement approach above, which doesn’t seem practical in this case.

Thanks for any help!

#11

This could be solved this way:

  1. Create a function returning Nth permutation:
Function NthPermut_Array(a(), n As Long)
  Dim iFrom As Long, iTo As Long, i As Long, j As Long, k As Long, x As Long
  iFrom = LBound(a)
  iTo = UBound(a)

  Dim pos(iFrom To iTo)
  For i = iTo - iFrom + 1 To 1 Step -1
    x = n Mod i
    j = iFrom - 1
    For k = 0 To x
      Do
        j = j + 1
      Loop While (Not IsEmpty(pos(j)))
    Next k
    pos(j) = iFrom + i - 1
    n = n \ i
  Next i

  Dim result(iFrom To iTo)
  For j = iFrom To iTo
    result(pos(j)) = a(j)
  Next j

  NthPermut_Array = result
End Function

Function NthPermut(s As String, n As Long)
  Dim size As Long, i As Long, s1 As String
  size = Len(s)
  Dim a(1 To size)
  For i = 1 To size
    a(size - i + 1) = Mid(s, i, 1)
  Next i

  NthPermut = Join(NthPermut_Array(a(), n), "")
End Function
  1. Use NthPermut with RANDBETWEEN:
A
1 abcdefg
2 =NTHPERMUT($A$1;RANDBETWEEN(0;PERMUT(LEN($A$1);LEN($A$1))-1))
3 =NTHPERMUT($A$1;RANDBETWEEN(0;PERMUT(LEN($A$1);LEN($A$1))-1))
…

This would create a sequence with as good randomness as RANDBETWEEN provides. Of course, it’s not the most performant implementation. E.g., this implementation (simply combining the two functions from above, sacrificing the universal implementation of the utility function that potentially may handle not only single characters of a string) is about twice as fast:

Function NthPermut(s As String, n As Long) As String
  Dim size As Long, i As Long, j As Long, k As Long, x As Long
  size = Len(s)

  Dim pos(1 To size)
  For i = size To 1 Step -1
    x = n Mod i
    j = 0
    For k = 0 To x
      Do
        j = j + 1
      Loop While (Not IsEmpty(pos(j)))
    Next k
    pos(j) = i
    n = n \ i
  Next i

  Dim result(1 To size)
  For j = 1 To size
    result(pos(j)) = Mid(s, j, 1)
  Next j

  NthPermut = Join(result,"")
End Function

If needed, RANDBETWEEN.NV could be used to make it non-volatile.
And indeed, using FACT(LEN($A$1)) in place of PERMUT(LEN($A$1);LEN($A$1)) would speed it up more.

1 Like
#12

First of all, thanks to everyone for their answers. Sorry it took me so long to get back to this – sick, then trying to catch up at work because I was sick.

Pretty much all the answers involve macros/user defined functions/etc. This is something I haven’t done with Calc before now, so I need to start by learning something about that, and then come back to this. Which I’ll do now. The first example is in Python, and I’m quite comfortable with Python – but didn’t know there was a Python interface in Calc.

Thank you again!

#2

Select the Row in Question plus the n Rows for the shuffled output (for Example A1:G100) and run:

from random import shuffle

def shuffle_first_row(*_):
    doc = XSCRIPTCONTEXT.getDocument()
    selection = doc.CurrentSelection
    data = selection.DataArray
    first, *_ = data
    first = list(first)
    out = [first[:]]
    for _ in range(len(data)-1):
        shuffle(first)
        out.append(first[:])
    selection.DataArray = out

shuffle_example.ods (8.6 KB)

1 Like
#4

Sorry. We crossed once more.

#3

You may start with Apache OpenOffice Community Forum - [Tutorial] Randomization in Calc - (View topic) for some background.
If you aren’t afraid of UserDefinedFunction(s) you may create your random permutations with this one:

Function randomPermutation(pNum, Optional pMakeColumn As Boolean)
If IsMissing(pMakeColumn) Then pMakeColumn = False
fa = createUnoService("com.sun.star.sheet.FunctionAccess") REM Some overhead?
Dim helper(pNum - 1, 0) As Double, j As Long, permutation
For j = 0 To pNum - 1
 helper(j, 0) = Rnd()
Next j
permutation = fa.callFunction("RANK",Array(helper, helper, 0))
If NOT pMakeColumn Then REM Default
 Redim res(0, pNum - 1) As Long
 For j = 0 To pNum - 1
  res(0, j) = permutation(j)(0)
 Next j
Else
 Redim res(pNum - 1, 0) As Long
 For j = 0 To pNum - 1
  res(j, 0) = permutation(j)(0)
 Next j
EndIf
randomPermutation = res
End Function

It isn’t optimized concerning efficiency, and uniqueness of the elements per row is only granted by the extremely long period of the pseudo-number-generator used by LibreOffice. .
How it can be used to create random shuffles of the content of adfjacent cells is demonstrated in this attachment:
randopemPermutationsAndUsage.ods (18.1 KB)

1 Like
#5

In this particular case the uniqueness is only derived from the possible number of permutations(7!) for a set of seven.

1 Like
#7

What’s “this particular case”?
As long as ordinary ranking of random numbers is involved and there are no checks, equally ranking elements are possible (in a fundamental sense).

1 Like
#8

as I said before: a set of seven provides only up to 5040 permutations, it doesnt matter the “quality of randomness” from random-number-generator.

1 Like
#9

My comment was not about the number of permutations as compared to the period of the PseudoRandomNumberGenerator (PRNG) what would have an impact on the probable repetition of sequences. It was about the chance to not get a correct permutation at all due to the repetion of an element.
If your “PRNG” has a period 5 this surely will matter for elements, and if repetitions of “random” numbers are to be expected occasionally with short distances, you will need to take in account the probability of “two equally ranking among 7” for the given task. RANDBETWEEN() can*t replace RAND() therefore when using the RANK() shuffle.
In fact LibreOffice (and most likely also Python) is using the currently prevailing Mersenne-twister MT19937 (-32).
I don’t know how the python routine you used is doing the shuffle. It may apply random transpositions, and by that avoid the above mentioned basical error, but will then also require at least a PRNG granting a (statistically) good random choice among N positions.

Function randomPermutationByTranspositions(pNum)
Dim helperP(1 To 1, 1 To pNum) As Long, helperR(1 To pNum) As Long, j As Long, h As Long
For j = 1 To pNum
 helperP(1, j) = j REM helperP is 2D to avoid problems with the output to a sheet.
 helperR(j) = randInt(1, pNum)
 REM That's CInt(Int(Rnd()*pNum) + 1
Next j
For j = 1 To pNum
 h = helperP(1, j)
 r = helperR(j)
 helperP(1, j) = helperP(1, r)
 helperP(1, r) = h
Next j
randomPermutationByTranspositions = helperP
End Function

(Editing:)
The variable helperR is superfluous. Can’t remember a plausible reason to introduce it.

1 Like
#6

random_ranks.ods (78.4 KB)

1 Like

Impressum (Legal Info) | Datenschutzerklärung (Privacy Policy)   Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.