Permutations 1

[Zathras]

Given a 5-element array of digits (1,2,3,4,5)

Describe an algorithm (and/or write the code) to generate the "next" permutation for a given permutation.

Define the "next" permutation as the smallest number larger than the current number where a number is composed of the elements of the array written from left to right.

E.g., here are the a few permutations in sequence:
[tt]
1,2,3,4,5 (first)
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
1,2,5,3,4
:
:
1,5,4,3,2
2,1,3,4,5
:
:
5,4,3,2,1 (last)
[/tt]
(Starting with 1,2,3,4,5 the application of the algorithm 119 times (in a loop) would generate all possible permutations.)

 

[SQLDenis]

is this correct?
120 rows
create TABLE #NumberPivot (NumberID INT PRIMARY KEY)
DECLARE @intLoopCounter INT
SELECT @intLoopCounter =1
WHILE @intLoopCounter <=5 BEGIN
INSERT INTO #NumberPivot
VALUES (@intLoopCounter)
SELECT @intLoopCounter = @intLoopCounter +1
END
GO

select * from #NumberPivot n1
join #NumberPivot n2 on n1.NumberID <> n2.NumberID
join #NumberPivot n3 on n3.NumberID <> n2.NumberID
and n3.NumberID <> n1.NumberID
join #NumberPivot n4 on n4.NumberID <> n2.NumberID
and n4.NumberID <> n1.NumberID
and n4.NumberID <> n3.NumberID
join #NumberPivot n5 on n5.NumberID <> n2.NumberID
and n5.NumberID <> n1.NumberID
and n5.NumberID <> n3.NumberID
and n5.NumberID <> n4.NumberID
order by 1,2,3,4

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[vongrunt]

OK that:

select top 5 identity(tinyint, 1, 1) as N into #blah from sysobjects

select * from #blah A cross join #blah B cross join #blah C cross join #blah D cross join #blah E
where A.N not in (B.N, C.N, D.N, E.N)
	and B.N not in (C.N, D.N, E.N)
	and C.N not in (D.N, E.N)
	and D.N not in (E.N)
order by A.N, B.N, C.N, D.N, E.N

But I think the question was about "next only" for any given permutation:

- input: 1 3 4 5 2
- output: ???

For change I'll do it with another language

------
[small]select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')[/small]

 

[SQLDenis]

so this

create TABLE #NumberPivot (N INT PRIMARY KEY)
DECLARE @intLoopCounter INT
SELECT @intLoopCounter =1
WHILE @intLoopCounter <=5 BEGIN
INSERT INTO #NumberPivot
VALUES (@intLoopCounter)
SELECT @intLoopCounter = @intLoopCounter +1
END
GO 

declare @string char(5)
select @string = '21345'

select  top 1 * from #NumberPivot n1
join #NumberPivot n2 on n1.N <> n2.N
join #NumberPivot n3 on n3.N <> n2.N
and n3.N <> n1.N
join #NumberPivot n4 on n4.N <> n2.N
and n4.N <> n1.N
and n4.N <> n3.N
join #NumberPivot n5 on n5.N <> n2.N
and n5.N <> n1.N
and n5.N <> n3.N
and n5.N <> n4.N
where convert(varchar,n1.N) + convert(varchar,n2.N) + convert(varchar,n3.N) + convert(varchar,n4.N) 
+ convert(varchar,n5.N) 
> @string
order by 1,2,3,4

Denis The SQL Menace
SQL blog:

http://sqlservercode.blogspot.com/

Personal Blog:

http://otherthingsnow.blogspot.com/

 

[PHV]

Brute force method in Excel VBA:
Sub setPermutations()
Dim i As Long, j As Long, k As Long, l As Long, m As Long
Dim r As Long
r = 1
For i = 1 To 5
For j = 1 To 5
For k = 1 To 5
For l = 1 To 5
For m = 1 To 5
If i <> j And i <> k And i <> l And i <> m _
And j <> k And j <> l And j <> m _
And k <> l And k <> m And l <> m Then
Cells(r, 1) = i: Cells(r, 2) = j: Cells(r, 3) = k: Cells(r, 4) = l: Cells(r, 5) = m
r = r + 1
End If
Next m
Next l
Next k
Next j
Next i
End Sub

 

[earthandfire]

I've taken vongrunt's solution for the core algorithm and generalised it

set nocount on

declare @input int
set @input = 12345

declare @chars int
set @chars = 1

create table #master (number int)
while @chars <= len(@input)
begin
	insert into #master values (@chars)
	set @chars = @chars + 1
end

declare @sql varchar(8000)
set @chars = 1
set @sql = 'select * from #master ' + char(@chars + 64)
while @chars < len(@input)
begin
	set @chars = @chars + 1
	set @sql = @sql + ' cross join #master ' + char(@chars + 64)
end
set @sql = @sql + ' where '
declare @chars2 int
set @chars = 1
while @chars < len(@input)
begin
	set @sql = @sql + char(@chars + 64) + '.number not in ('
	set @chars2 = @chars + 1
	while @chars2 < len(@input)
	begin
		set @sql = @sql + char(@chars2 + 64) + '.number, '
		set @chars2 = @chars2 + 1
	end
	set @sql = @sql + char(@chars2 + 64) + '.number) and '
	set @chars = @chars + 1
end
set @sql = substring(@sql, 1, len(@sql) - 4)
set @sql = @sql + ' order by '
set @chars = 1
while @chars < len(@input)
begin
	set @sql = @sql + char(@chars + 64) + '.number, '
	set @chars = @chars + 1
end
set @sql = @sql + char(@chars + 64) + '.number'

exec (@sql)

drop table #master
set nocount off

 

[sedj]

... and that children, is why SQL should be left for selecting data, not for programming algorithms !

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[vongrunt]

I'm just testing VB(Script) example... freakin' arrays, gotta migrate to C# soon :E

------
[small]select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')[/small]

 

[Zathras]

Brute force wasn't exactly what I had in mind.

Building all possible combinations, selecting the ones that produce a number greater than the given number, sorting and then taking the smallest is clever, but is not what I would call an algorithm for finding the "next" permutation.

What if the array has 100's or 1000's of elements?

 

[skiflyer]

Well, I think the interesting task here is to figure out what the next value is given any valid permutation... and I think it's best solved via recursion...

Basically, you have a given permutation:

1,2,3,5,4

You take the last two and say, is that the greatest permutation for them (5,4)... yes... well then take the last three and give me the smallest permutation > 3,5,4... this is 4,3,5

So now we have 1,2,4,3,5 and we take the last two, and say is that greatest permutation (3,5)... no? then give me the next permutation for those 2... 5,3... so we have
1,2,4,5,3... the last two, greatest (5,3).. yes, so give me the last 3 (4,5,3)... greatest? no so give mthe next (5,3,4)

Anyway, not quite that simple, but I'll try to code it up and see how it goes.

 

[vongrunt]

Scan digits right-to-left.
Find first position where next digit gets smaller (3 5)
Swap this digit with next greater digit (3 with 4)
Sort the rest (w/o bubble sort of course) (5, 3) => (3, 5)

Hm...



------
[small]select stuff(stuff(replicate('<P> <B> ', 14), 109, 0, '<.'), 112, 0, '/')[/small]

 

[PHV]

A VBA or VBS attempt.

Option Explicit
Public myArr(119)
Sub setPermutations()
Dim i, j, k, l, m
Dim r
r = 0
For i = 1 To 5
  For j = 1 To 5
    For k = 1 To 5
      For l = 1 To 5
        For m = 1 To 5
          If i <> j And i <> k And i <> l And i <> m _
          And j <> k And j <> l And j <> m _
          And k <> l And k <> m And l <> m Then
            myArr(r) = Val(i & j & k & l & m)
            r = r + 1
          End If
        Next
      Next
    Next
  Next
Next
End Sub

Function getNextPermutation(cur)
If myArr(0) = 0 Then setPermutations
Dim i
For i = 0 To UBound(myArr)
  If myArr(i) > cur Then Exit For
Next
If i <= UBound(myArr) Then getNextPermutation = myArr(i)
End Function

And the reply to the OP
MsgBox getNextPermutation(Val(Join(Array(1,2,3,4,5),"")))

Hope This Helps, PH.
Want to get great answers to your Tek-Tips questions? Have a look at FAQ219-2884 or FAQ181-2886

 

[skiflyer]

I say vongrunt has it, but sort only those things to the right of the larger of the swapped numbers.

 

[skiflyer]

Wait a minute vongrunt, you tricked me... that was the first thing I tried and it doesn't work at all!

I still say recursion is the best solution as I laid it out, but I'm out of time to program it... maybe I'll come back later.

Where vongrunt's idea breaks down...

1,2,3,5,4

next value should be
1,2,4,3,5
but the above idea results in
1,2,5,3,4

 

[ca8msm]

Yeah, I reckon recursion might be a way to get it as well. I'll try an example tomorrow I think but at the moment, I'm thinking of using the method I used in thread796-1195039.


____________________________________________________________

Need help finding an answer?

Try the Search Facility or read FAQ222-2244 on how to get better results.

 

[Zathras]

I would say vongrunt just about has it, but there is an implied assumption that should probably be stated explicitly.

For example, apply the algorithm to: 1,4,3,5,2

"Swap this digit with next greater digit (3 with 4)" does not quite do it.

 

[Tarwn]

Well, I worked this out on the way home and it looks like several others were headed down the same road (heh, no pun intended) of thought:

import copy
def getPerm(aList,sort=True):
	t_list=[]
	if sort: aList.sort()
	for item in aList:
		if len(aList) > 1:
			w_list = copy.copy(aList)
			w_list.remove(item)
			for perm in getPerm(w_list,False):
				perm.insert(0,item)
				t_list.append(perm)
		else:
			t_list.append([item])
	return t_list

Just pass it a list and it passes back a list of lists (in the correct order). You can make it break by passing it an unorderd list and a False for sort, but what the hey
Test Code:

a=[3,4,2,1,5]
print getPerm(a)

Still think I could do it in less lines, I'll have to try another language, my Python is rusty.

-T

 

[Mastakilla]

I know it's not elegant code but how about this:

i've created a class in vb.net,

you give the array of digits to its only public function and it'll retrun the next smallest combination.

Public Class PermutationBrainFood


    Private GivenNumber As Integer
    Private MaxNumber As Integer
    Private OriginalArray As Integer()


    Public Function GiveNextResult(ByVal myIntArray As Integer())

        OriginalArray = myIntArray

        GivenNumber = getNumberFromArray(OriginalArray)

        MaxNumber = getMaxNumber()

        If GivenNumber = MaxNumber Then
            Return GivenNumber
        Else

            For result As Integer = GivenNumber + 1 To MaxNumber

                If numberIsValid(result) Then
                    Return result
                    Exit For
                End If

            Next

        End If

    End Function



    Private Function getNumberFromArray(ByVal myArray As Integer()) As Integer

        Dim tempString As String = ""

        For i As Integer = 0 To myArray.GetUpperBound(0)

            tempString &= myArray.GetValue(i).ToString

        Next

        If tempString <> "" Then
            Return CInt(tempString)
        Else
            Return 0
        End If

    End Function

    Private Function getMaxNumber() As Integer

        Dim CanExitLoop As Boolean
        Dim tempInt As Integer

        If OriginalArray.Length <> 0 Then

            Dim onePermutationAchieved As Boolean

            While Not CanExitLoop

                onePermutationAchieved = False

                For i As Integer = 1 To OriginalArray.GetUpperBound(0)

                    If OriginalArray.GetValue(i) > OriginalArray.GetValue(i - 1) Then

                        tempInt = OriginalArray.GetValue(i)
                        OriginalArray.SetValue(OriginalArray.GetValue(i - 1), i)
                        OriginalArray.SetValue(tempInt, i - 1)

                        onePermutationAchieved = True

                    End If

                Next

                If Not onePermutationAchieved Then
                    CanExitLoop = True
                End If

            End While

            Return getNumberFromArray(OriginalArray)

        Else

            Return 0

        End If




    End Function

    Private Function numberIsValid(ByVal number As Integer) As Boolean

        Dim tempString As String

        tempString = CStr(number)

        For i As Integer = 0 To OriginalArray.GetUpperBound(0)

            If tempString.IndexOf(OriginalArray.GetValue(i).ToString) = -1 Then
                Return False
                Exit Function
            End If

        Next

        Return True

    End Function



End Class

 

[Mastakilla]

well it returns then next combination as a number, if forgot to return it as an array of digits..

 

[earthandfire]

Variation to allow for a specific starting point. This handles upto 26 digits. It is still based on vongrunt's core algorithm - but I've made a few changes to allow for the extra flexibility. I've also split the sql up to ensure that there is no chance of exceeding the varchar limit.

set nocount on

declare @input varchar(26)
set @input = '31245'

if len(@input) > 26
begin
	print 'Maximum 26 elements'
end
else
begin
	declare @chars int
	set @chars = 1

	create table #master (n int)
	while @chars <= len(@input)
	begin
		insert into #master values (@chars)
		set @chars = @chars + 1
	end

	create table #temp(n int identity (1, 1))
	declare @sql varchar(8000)
	set @sql = 'alter table #temp add '
	set @chars = 1
	while @chars < len(@input)
	begin
		set @sql = @sql + char(@chars + 64) + ' varchar(1), '
		set @chars = @chars + 1
	end
	set @sql = @sql + char(@chars + 64) + ' varchar(1), result varchar(26)'
	exec (@sql)

	set @sql = 'insert into #temp ('
	set @chars = 1
	while @chars < len(@input)
	begin
		set @sql = @sql + char(@chars + 64) + ', '
		set @chars = @chars + 1
	end
	set @sql = @sql + char(@chars + 64) + ') '
	set @sql = @sql + 'select '
	set @chars = 1
	while @chars < len(@input)
	begin
		set @sql = @sql + char(@chars + 64) + '.n, '
		set @chars = @chars + 1
	end
	set @sql = @sql + char(@chars + 64) + '.n from #master '
	set @chars = 1
	set @sql = @sql + char(@chars + 64)
	while @chars < len(@input)
	begin
		set @chars = @chars + 1
		set @sql = @sql + ' cross join #master ' + char(@chars + 64)
	end
	set @sql = @sql + ' where '
	declare @chars2 int
	set @chars = 1
	while @chars < len(@input)
	begin
		set @sql = @sql + char(@chars + 64) + '.n not in ('
		set @chars2 = @chars + 1
		while @chars2 < len(@input)
		begin
			set @sql = @sql + char(@chars2 + 64) + '.n, '
			set @chars2 = @chars2 + 1
		end
		set @sql = @sql + char(@chars2 + 64) + '.n) and '
		set @chars = @chars + 1
	end
	set @sql = substring(@sql, 1, len(@sql) - 4)
	set @sql = @sql + ' order by '
	set @chars = 1
	while @chars < len(@input)
	begin
		set @sql = @sql + char(@chars + 64) + '.n, '
		set @chars = @chars + 1
	end
	set @sql = @sql + char(@chars + 64) + '.n'
	exec (@sql)
	set @sql = 'update #temp set result = '
	set @chars = 1
	while @chars < len(@input)
	begin
		set @sql = @sql + 'convert(varchar, ' + char(@chars + 64) + ') + '
		set @chars = @chars + 1
	end
	set @sql = @sql + 'convert(varchar, ' + char(@chars + 64) + ')'
	exec(@sql)
	select result from #temp where result >= @input
	
	drop table #temp
	drop table #master
end

set nocount off