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

 

[Tarwn]

I almost had one in VBScript in 14 lines based off text manipulation...but it breaks for more then 3 numbers and the key lines wraps a few times...my head hurts too much to try and figure out whats wrong with it

 

[earthandfire]

My final attempt at this one. This version allows for non-numeric data - but sorting is ASCII/ANSI based so the key has to be in the correct order without gaps.

set nocount on

declare @key varchar(26)
set @key = 'ABCDEF'
declare @input varchar(26)
set @input = 'EFABCD'

if len(@input) > 26 or len(@input) = 0 or len(@input) <> len(@key)
begin
	print 'Maximum 26 elements, input and keyorder must be same size and input cannot be empty'
end
else
begin
	declare @chars int
	set @chars = 1

	create table #master (n int, k char(1))
	while @chars <= len(@input)
	begin
		insert into #master values (@chars, substring(@key, @chars, 1))
		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(1), (select k from #master where n = ' + char(@chars + 64) + ')) + '
		set @chars = @chars + 1
	end
	set @sql = @sql + 'convert(varchar(1), (select k from #master where n = ' + char(@chars + 64) + '))'
	exec(@sql)
	select result from #temp where result >= @input
	
	drop table #temp
	drop table #master
end

set nocount off

 

[vongrunt]

Let's do it w/ J(ava)Script:

<%	@Language = "JScript" %>
<%
	var aDigits = new Array( 1, 2, 3, 4, 5 );
	var iCycle=0;
	
	// display results until there are no more permutations
	do
	{	Response.write( "Perm. #" + (++iCycle) + ": " + aDigits.join(", ") + "<br>" );
	}
	while (	nextPermutation( aDigits ) );
	
	
	//-----
	function nextPermutation( aDigits )
	{	var iCnt = aDigits.length;
		
		// right-to-left scan; find swap point (negative slope)
		for( var i= iCnt-1; i>=0; i-- )
			if( aDigits[i] < aDigits[i+1] ) break;
			
		// no negative slope = everything sorted descending = no next permutation	
		if( i < 0 ) return false;
		
		// find smallest greater value right from swap point
		for( var s=i+1, j=s; j<=iCnt; j++ )
			if( aDigits[j] > aDigits[i] && aDigits[j] < aDigits[s] )
				s = j;

		// swap these two values				
		swapItems( aDigits, i, s );
		
		// flip the rest :P
		for( j = i+1, iCnt--; j<iCnt; j++, iCnt-- )
			swapItems( aDigits, j, iCnt );		
	
		return true;
	}	
	
	//-----
	function swapItems( arr, n1, n2 )
	{	var tmp = arr[n1];
		arr[n1] = arr[n2];
		arr[n2] = tmp;
	}
%>

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

 

[ca8msm]

OK, here's my attempt with .NET (using a recursive function):

Step 1 - Declare Variables

    [COLOR=blue]Dim[/color] myArray [COLOR=blue]As[/color] [COLOR=blue]New[/color] ArrayList
    [COLOR=blue]Dim[/color] blnNextValue [COLOR=blue]As[/color] [COLOR=blue]Boolean[/color] = [COLOR=blue]False[/color]
    [COLOR=blue]Dim[/color] nextValue [COLOR=blue]As[/color] [COLOR=blue]String[/color] = ""

Step 2 - The function to populate those variables

    [COLOR=blue]Private[/color] [COLOR=blue]Sub[/color] GetPermutationArrayList([COLOR=blue]ByVal[/color] PrefixString [COLOR=blue]As[/color] [COLOR=blue]String[/color], [COLOR=blue]ByVal[/color] Permutation [COLOR=blue]As[/color] [COLOR=blue]String[/color], [COLOR=blue]ByRef[/color] GlobalArrayList [COLOR=blue]As[/color] ArrayList, [COLOR=blue]ByVal[/color] returnValueAfter [COLOR=blue]As[/color] [COLOR=blue]String[/color], [COLOR=blue]Optional[/color] [COLOR=blue]ByVal[/color] minimumLength [COLOR=blue]As[/color] [COLOR=blue]Integer[/color] = 1)
        [COLOR=blue]If[/color] PrefixString.Length >= minimumLength [COLOR=blue]AndAlso[/color] myArray.IndexOf(PrefixString) = -1 [COLOR=blue]Then[/color] myArray.Add(PrefixString)
        [COLOR=blue]If[/color] blnNextValue = [COLOR=blue]True[/color] [COLOR=blue]AndAlso[/color] PrefixString.Length >= minimumLength [COLOR=blue]Then[/color] nextValue = PrefixString : blnNextValue = [COLOR=blue]False[/color]
        [COLOR=blue]If[/color] PrefixString = returnValueAfter [COLOR=blue]Then[/color] blnNextValue = [COLOR=blue]True[/color]
        [COLOR=blue]For[/color] intIndex [COLOR=blue]As[/color] [COLOR=blue]Integer[/color] = 1 [COLOR=blue]To[/color] Permutation.Length
            GetPermutationArrayList(PrefixString & Permutation.Substring(intIndex - 1, 1), Permutation.Substring(0, intIndex - 1) & Permutation.Substring(intIndex), GlobalArrayList, returnValueAfter, minimumLength)
        [COLOR=blue]Next[/color]
    [COLOR=blue]End[/color] [COLOR=blue]Sub[/color]

Step 3 - Call the function

        GetPermutationArrayList("", "12345", myArray, "15432", 5)

The "myArray" variable will contain an array of all the permutations (in order) and the "nextValue" variable will contain the permutation after the one specified in the 4th argument of the call.

That's a total of 12 lines which includes declaring the variables, the function itself and the call to the function.


____________________________________________________________

Need help finding an answer?

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

 

[chrissie1]

step 3 - for dummies

try
  GetPermutationArrayList("", "12345", myArray, "15432", 5)
catch(ex as exception)
  messagebox.show("probably a runningoutofstackspaceerror.")
end try

Christiaan Baes
Belgium

"My new site" - Me

 

[ca8msm]

____________________________________________________________

Need help finding an answer?

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

 

[vongrunt]

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

Mea culpa & my Bantu English...

For this case swap point occurs at 3rd location (3 is smaller than 5). And smallest value on the right side greater than 3 is 5. After that swap set contains 1,4,5,3,2. Sort remaining values (5, 2). IMHO there is no need for sorting algorithm or recursion - just flip remaining values - (5, 2) becomes (2, 5). All together: 1,4,5,2,3.

Another example: 1,5,4,3,2

Swap point occurs at 1st location (1 < 5)
2 is next value in to the right greater than 1. Swap 'em.
After swap set contains 2, 5, 4, 3, 1
Flip everything right from the initial swap point (5, 4, 3, 1) -> (1, 3, 4, 5)
Set contains 2, 1, 3, 4, 5.

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

 

[Zathras]

That is exactly what I was looking for vongrunt! I knew you hade the answer but just weren't expressing it completely.

I'll overlook the typo where you have (5,2) becomes (2,5) when you really mean (3,2) becomes (2,3).

As for the .Net and Java solutions, I don't have the expertise (or the software) to verify whether they are correct or not. But the proof of the pudding....

 

[Tarwn]

I realized earlier that I had mistakenly create a function to find all permutations rather then just the next permutation. Here is new code to find only the next permutation (if one exists):

def getNextPerm(aList):
	p=[aList.pop(-1)]
	while len(aList) > 0:
		p[0:0] = [aList.pop(-1)]
		if p[0]<p[1]: return aList.extend(sortish(p,p[0],[]))

def sortish(sList,top,result=[]):
	while(len(sList)>0): result[((sList.pop(sList.index(max(sList))))<=top):0] = [(sList[(sList.index(max(sList)))])]
	return result

and the code to execute and print it:

a=[1,2,3,4,5]
getNextPerm(a)
print "next is: " + str(a)

8 lines of code plus 3 lines to push out an example, total of 11 lines without any line continuations. To print out all permutations from after a starting point would take 10 lines

Here is a commented and slightly extended version:

def getNextPerm(aList):
	#pop the last item and start a new list
	p=[aList.pop(-1)]
	#while there are items in the original list
	while len(aList) > 0:
		#insert the last item from the original into the temp list
		p[0:0] = [aList.pop(-1)]
		#if the front entry is smaller then the second entry
		if p[0]<p[1]: 
			#call sortish() on the temporary list and then append the results to the remains of the original list
			return aList.extend(sortish(p,p[0],[]))

#sList is the list to sortish on, top is the first number of the list, result is an empty list (hopefully)
def sortish(sList,top,result=[]):
	#while the original list has items in it
	while(len(sList)>0): 
		#pop the largest item out of the list
		s = sList.pop(sList.index(max(sList))) 
		#if this number is smaller or equal to the top, insert it to the second position in the list
		if s<=top: 
			result[1:0] = [s]
		else: 
			#otherwise insert it at the beginning of the string
			result[0:0] = [s]
	return result

 

[BoxHead]

Here's an Access VBA function to return the next permutation. I had started out working on the 12345 question more literally than I should have so this only works up to 9 digits, but it does just give the next permutation.

Public Function getNextPerm(myGiven As Single) As Single
Dim myStr As String, myChk As Single, myMax As Single, myComp As Integer, X As Integer, Y As Integer
myStr = myGiven

For X = Len(myStr) To 1 Step -1 'Get the maximum permutation
myMax = myMax & X
Next X
myChk = myGiven
Do While myChk < myMax
myChk = 9 + myChk
myStr = myChk
myComp = 0
For Y = 1 To Len(myStr)
myComp = myComp + (Len(myStr) - ((Len(Replace(myStr, Mid(myStr, Y, 1), "")) + IIf(InStr(myMax, Mid(myStr, Y, 1)) > 0, 1, 0))))
Next Y
If myComp = 0 Then

getNextPerm = myChk
Exit Do
End If
Loop
getNextPerm = myChk


End Function

Fun stuff!



When Galileo theorized that Aristotle's view of the Universe contained errors, he was labeled a fool.
It wasn't until he proved it that he was called dangerous.