Here's the problem; I need to write a recursive function that outputs permutations for a given input n; such that the output looks like:

Given n=3, you'd get. . .

empty set
1
1 2
1 3
2
2 3
3
1 2 3

The order in which the subsets are generated does not matter.


class genPerms {

public static void main(String[] args){
System.out.print("empty set");
genPerm(3); }

public static void genPerm(int n) {

int[] appendings = new int[0];

recursiveGenPerm(n, appendings);}

public static void recursiveGenPerm(int n, int[] appendings2) {

if(n == 0) {

for(int v = 0; v < appendings2.length; v++){
System.out.print(appendings2[v]);}
System.out.println();}

else{
recursiveGenPerm(n-1, appendings2);
int[] B = new int[appendings2.length+1];
B[0] = n;
for(int c=1; c < B.length; c++){
B[c] = c+1;}
recursiveGenPerm(n-1, B);
}
}}

This is my code thus far, which outputs:

empty set
1
2
12
3
12
22
123

Obviously, I have a problem with 2 of the lines (the second 12 and the 22), any ideas on how to fix this? I think it's a problem with how I copy appendings to B but I'm not positive. Any help would be appreciated.

Recursion is strange in that it's a simple concept but can be incredibly complex and hard to understand. I wasn't really understanding your approach to the problem, so I worked out my own form of a solution.

class genPerms
{
	public static void main(String[] args)
	{
		int num = 3;
		
		if(args.length > 0)
		{
			num = Integer.parseInt(args[0]);
		} 
		
		showPermutations(num);
	}
	
	public static void showPermutations(int number)
	{
		showPermutations(number, 1, 1);
	}
	
	public static void showPermutations(int number, int start, int current)
	{
		if(current <= number)
		{
			String output = "";
			
			for(int x = start; x <= current; x++)
			{
				if(output.length() > 0) output += " ";
				output += x;
			}
			
			System.out.println(output);
			
			showPermutations(number, start, current + 1);
		}
		else if(start <= number)
		{
			showPermutations(number, start + 1, start + 1);
		}
		else
		{
			System.out.println("Empty Set");
		}
	}
}

I'll continue to look at your code and see if I can find the logic errors. Hopefully, if you study what I did, you can understand the problem a bit better.

The solution I came up with allows you to specify a number other than 3 but defaults to 3 if no argument is given. There isn't any error checking on the input, so supplying a non-integer number will crash the program.

I also added spaces between the numbers so that you could specify numbers larger than 9 and read the output easily.

This article has been dead for over six months. Start a new discussion instead.