Permutations/Combinations of a set of numbers

[bridgesmadeofsweets]

Hello,

I have looked through the forum for existing answers to this but can't find a response that I understand enough to modify to my own design.

Basically I want to output every combination of a set of numbers. These permutations must include combinations that use only a few of the numbers as well as all eight...ie.

1,
1,2
1,2,3
as well as 1,2,3,4,5,6,7,8

The macro below is from
http://www.j-walk.com/ss/excel/tips/tip46.htm
This only produces combinations using every number. I'm not sure how this macro works but hopefully someone with better know how could run with it or break it down for me!

I only need to achieve this once but am pretty sure doing it manually will cause error and or madness!

Any help would be much appreciated!</PRE>
Kind Regards</PRE>
Joe</PRE>


Dim CurrentRowSub GetString() Dim InString As String InString = InputBox("Enter text to permute:") If Len(InString) < 2 Then Exit Sub If Len(InString) >= 8 Then MsgBox "Too many permutations!" Exit Sub Else ActiveSheet.Columns(1).Clear CurrentRow = 1 Call GetPermutation("", InString) End IfEnd SubSub GetPermutation(x As String, y As String)' The source of this algorithm is unknown Dim i As Integer, j As Integer j = Len If j < 2 Then Cells(CurrentRow, 1) = x & y CurrentRow = CurrentRow + 1 Else For i = 1 To j Call GetPermutation(x + Mid(y, i, 1), _ Left(y, i - 1) + Right(y, j - i)) Next End IfEnd Sub</PRE>
</PRE>

 

[mikerickson]

Are you asking for a formula to generate the series

001
002
003
...
009
010
011
012
...
099
101
...
999

 

[bridgesmadeofsweets]

i want to something to do this:

say i had 1 , 2 + 3 - i would want excel to output:

1
2
3
12
13
21
23
31
32
123
132
213
231
312
321

only with 8 digits...eg. 1 , 2, 3, 4, 5, 6, 7, 8 - and I can't figure out a sensible way to do it with my mind alone.

 

[mikerickson]

I'm at work so I'll have to work on this later, but...

A) It looks like you want no number to be duplicated (i.e. 131 is not on your list), is that the case?

2) What is the purpose of this list?
Listing all possible combinations is usually not the best way to get results.

These kinds of lists are very aminable (sp?) to analysis and that analysis is much faster than listing all combinations.

 

[mikerickson]

Interesing problem. I have a method to generate the list.

First some notation:

Let SS8 be the set of all non-empty subsets of {1,2,3,4,5,6,7,8}
Let P be the set of all permutations of {1,2,3,...,n}
e.g P(3) = { {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1} }

This flow-chart pseudo-code should produce the list you want

For each subSet in SS8
    For each permutation in P(UBound(subSet))
        Output (permutation acting on subSet)
    Next permutation
Next subSet

where the permutation {3,2,1} acting on the set {a,b,c,d} is the set {c,b,a,d}

Since there are n! permutation in P and there are 2^8 sub-sets of {1,2..,7,8}, this totals out to 109,600 items in the list you want. Achieving this in less than glacial time without overflowing memory is where I'm at right now.

 

[bridgesmadeofsweets]

Hello,

Thanks for running with this! - wow - 109,600 items! I thought it might get a bit huge!

I might need some help understanding how to generate the list from your notes so far - I can tell you're on the right track but I'm too much of a novice to transform the pseudo code into a macro. Once the list exists I wouldn't need to do the task again so I'm okay with the process of originating it being a bit clunky or leaving my computer to generate it for a good long while - or am I totally underestimating just how long it might take?

I also thought I should give some context to my query although it might cause some shaking of heads....maybe I just like huge spreadsheets too much!

To contextualise, the purpose of the list is this:

I have an excel spreadsheet containing every word in the scrabble dictionary.

I want to create a front end for this that allows the user to enter up to 8 letters into a cell. The spreadsheet would then return every approved word possible from this collection of letters (plus its scrabble score) to the user.

This isn't for use during the game but as a aid for practising ie. pull up to 8 letters from the bag, come up with the best words you can with your mind then use the spreadsheet front end to easily see what you have missed.

My thinking is -

Create a sheet with all the permutations of 1,2,3,4,5,6,7,8 which will be used to pull apart the letters the user has entered into every arrangement possible.

The massive list of letter combinations is then referenced against the scrabble dictionary data and approved words compiled in a new sheet for the user to see.

The issue for me is originating the initial vast collection of numbers.
I have managed to make all the other elements work.

I hope this doesn't confuse - I just thought it might help to see where I heading with this.

 

[Gerald Higgins]

In that case, don't you just need every number from 1 to 87,654,321

EXCEPT for the following numbers, which need to be excluded
a) Any number containing the digit 0
b) Any number containing the digit 9
c) Any number containing two or more occurrences of any single digit

One way to do this, maybe not the best way, would be to put a 1 in cell A1, and then

=a1+1

in A2, and copy down.

In versions of Excel before 2007, you'd need at least two columns to do this, assuming Mike's calculation of 109,600 permutations is correct.

Then, you could use text analysis formulas to flag up the numbers to be rejected.

For example, to flag numbers containing the digit 0, put a formula like this in Col B

=if(iserror(search("0",A1,1)),0,1)

will put a 0 in col B if there is NOT a 0 in A1, and will put a 1 in Col B if there IS a 0 in A1.
You can then filter the results.
You can use similar formulas for the other excluded number groups.

 

[pgc01]

Create a sheet with all the permutations of 1,2,3,4,5,6,7,8 which will be used to pull apart the letters the user has entered into every arrangement possible.

I have managed to make all the other elements work.

Hi

If you just need the permutations of single digits, try:

Sub AllPermutations()
Dim arr As Variant, lRow As Long
 
arr = Array(1, 2, 3, 4)
 
Columns("A").Clear
Application.ScreenUpdating = False
Permut "", Join(arr, ""), lRow
 
Columns("A").Sort key1:=Range("A1"), order1:=xlAscending, Header:=xlNo
Application.ScreenUpdating = True
End Sub
 
Sub Permut(ByVal sPermut1 As String, ByVal sPermut2 As String, ByRef lRow As Long)
Dim j As Long, s As String
 
For j = 1 To Len(sPermut2)
    lRow = lRow + 1
    s = Mid(sPermut2, j, 1)
    Cells(lRow, "A") = sPermut1 & s
    If Len(sPermut2) > 1 Then Permut sPermut1 & s, Replace(sPermut2, s, ""), lRow
Next j
End Sub

 

[ajetrumpet]

I copied the routine from the file link that you originally provided, and I added a twist. Here it is:

Sub GetString()
    Dim InString As String
    InString = InputBox("Enter text to permute:")
    If Len(InString) < 2 Then Exit Sub
    If Len(InString) >= 8 Then
        MsgBox "Too many permutations!"
        Exit Sub
    Else
        ActiveSheet.Columns(1).Clear
        CurrentRow = 1
        Call GetPermutation("", InString)
    End If
End Sub

Sub GetPermutation(x As String, y As String)
'   The source of this algorithm is unknown
    Dim i As Integer, j As Integer

j = Len(y)

Do Until j = 0
    
    If j < 2 Then
        Cells(CurrentRow, 1) = x & y
        CurrentRow = CurrentRow + 1
    Else
        For i = 1 To j
            Call GetPermutation(x + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
  j = j - 1

Loop

End Sub

It doesn't do the job completely (and has duplicates too), but it gets more than you got before. I don't have time to spend on it, but I thought I would show you this, just because it might spark some more ideas in YOUR head about what to do. It was simply an experiment...

 

[ajetrumpet]

Here's another interesting combo in the procedure:

Sub GetPermutation(x As String, y As String)
'   The source of this algorithm is unknown
    Dim i As Integer, j As Integer, countdown As Integer

countdown = Len(y)

j = countdown

Do Until j = 0

    If j < 2 Then
        Cells(CurrentRow, 1) = x & y
        CurrentRow = CurrentRow + 1
    Else
        For i = 1 To j
            Call GetPermutation(x + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
            j = j - 1

Loop

End Sub

Again it doesn't give you everything, and no thinking on my part, but it's more.