Permutations 1

Status
Not open for further replies.

Zathras

Programmer
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.)

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:
Personal Blog:

OK that:
Code:
``````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]

so this

Code:
``````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:
Personal Blog:

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

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

Code:
``````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``````

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

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

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]

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?

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.

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]

A VBA or VBS attempt.
Code:
``````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

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

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

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.

____________________________________________________________

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

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.

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:
Code:
``````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:
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

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.

Code:
``````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``````

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

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.

Code:
``````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``````

Status
Not open for further replies.