Help doing recursion

[Chris]

Help please. I want to print out all the ordered permutation that a
list of items can take but the problem here is I need as many forloops
as there are items and in the real program it is not possible to
determine that at compile time. To solve this I would obviusly need
to do it recursively but I simply can't think in terms of recursion.
Any kind soul wanna help out PLEASE?

public static void main(String[] args){
int numberofitems =4;
int maxnumberofvaluesforanitem = 3;

Vector firstitem = new Vector();
firstitem.addElement("1");
firstitem.addElement("2");
firstitem.addElement("3");

Vector seconditem = new Vector();
seconditem.addElement("4");
seconditem.addElement("5");

Vector thirditem = new Vector();
thirditem.addElement("6");
thirditem.addElement("7");

Vector fourthitem = new Vector();
fourthitem.addElement("8");
fourthitem.addElement("9");

for(int a=0; a<firstitem.size();a++){
for(int b=0;b<seconditem.size();b++){
for(int c=0;c<thirditem.size();c++){
for(int d=0;d<fourthitem.size();d++){
System.out.println((String)firstitem.elementAt(a) +
(String)seconditem.elementAt(b) +
(String)thirditem.elementAt(c) +
(String)fourthitem.elementAt(d) );
}
}
}
}

Would result

1,4,6
1,4,7
2,4,6
2,4,7
3,4,6
3,4,7
1,5,6
1,5,7
2,5,6
2,5,7
3,5,6
3,5,7

 

[Sajjad Lateef]

Help please. I want to print out all the ordered permutation that a
list of items can take but the problem here is I need as many forloops
as there are items and in the real program it is not possible to
determine that at compile time. To solve this I would obviusly need
to do it recursively but I simply can't think in terms of recursion.

I think that this can be done procedurally, too. You will need
about three nested loops. A little more complicated, but, fun to write.

Hint: Think in terms of creating an array of Strings for each
element in Vector and use that as input when processing the next Vector.

Innermost-loop 1:
Input: []
Output: ["1", "2", "3"]

Innermost-loop 2:
Input: ["1", "2", "3"]
Output: ["1,4", "1,5", "2,4", "2,5", "3,4", "3,5"]

Innermost-loop 3:
Input: ["1,4", "1,5", "2,4", "2,5", "3,4", "3,5"]
Output: ["1,4,6", "1,5,6", "2,4,6" ... ]

Later, remove any duplicates.

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

Help please. I want to print out all the ordered permutation that a
list of items can take but the problem here is I need as many forloops
as there are items and in the real program it is not possible to
determine that at compile time. To solve this I would obviusly need
to do it recursively but I simply can't think in terms of recursion.
Any kind soul wanna help out PLEASE?

Hopefully this will be readable. The print(List v) will print the
permutations of the Vectors contained in a Vector. Basically, you put
all your Vectors into one big Vector. The idea here is to have an int
array representing the indices to print from each vector. After printing
one permutation we increment the right most index in the array if it is
lesser than the size of the vector -1, else we set it to zero and try to
increment the next index. If we reach the first element in the array and
we can no longer increment it without going out of bounds, we end the
recursion, else we print the next permutation using the changed array.
Try reading the code, it should be quite clear.

public static void print(List v)
{
int[] arr = new int[v.size()];
print(v, arr);
}

public static void print(List v, int[] arr)
{
for (int i = 0; i < v.size(); i++)
{
List l = (List) v.get(i);
System.out.print((String) l.get(arr) + " ");
}

System.out.print("\n");

for (int i = arr.length - 1; i >= 0; i--)
{
List l = (List) v.get(i);
if (arr < l.size() - 1)
{
arr = arr + 1;
print(v, arr);
break;
}
else
{
if (i == 0)
{
break;
}
else
{
arr = 0;
}
}
}
}

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

public static void print(List v, int[] arr)
{
for (int i = 0; i < v.size(); i++)
{
List l = (List) v.get(i);
System.out.print((String) l.get(arr) + " ");
}

System.out.print("\n");

for (int i = arr.length - 1; i >= 0; i--)
{
List l = (List) v.get(i);
if (arr < l.size() - 1)
{
arr = arr + 1;
print(v, arr);
break;
}
else
{
if (i == 0)
{
break;
}
else
{
arr = 0;
}
}
}
}

Come to think of it, there is no compelling reason to use recursion
here. You could just as well put the above in a while(true) loop. But
I'll leave that as an excersize to you.

 

[Tr0mBoNe-]

public static void print(List v, int[] arr)
{
for (int i = 0; i < v.size(); i++)
{
List l = (List) v.get(i);
System.out.print((String) l.get(arr) + " ");
}

System.out.print("\n");

for (int i = arr.length - 1; i >= 0; i--)
{
List l = (List) v.get(i);
if (arr < l.size() - 1)
{
arr = arr + 1;
print(v, arr);
break;
}
else
{
if (i == 0)
{
break;
}
else
{
arr = 0;
}
}
}
}

Come to think of it, there is no compelling reason to use recursion
here. You could just as well put the above in a while(true) loop. But
I'll leave that as an excersize to you.

In discrete mathematics, the number of permutations of a group without
repetition is the (total number of elements)Factorial divided by [(the
total number of elements) - (the number you can choose each time)]

for example, the number of telephone numbers you can have is P(10, 4),

or

10!/(10 - 4)! = 5040 phone numbers.
if you perform this test at the start of the program, then you would
know how many permutations you would need. With permutations, you
can't really do it recursivly, as it is often you could be hit with an
infinate set, like the integers. If you can write a program that could
produce all the permutations of the set of the integers crossed with
the set of the integers, you would need one phat computer to do that.

In order to make this program as scalable as possible, you must create
a function (or method, ive been programming c so long i think i have
gone to the dark side) that could take the input of how many elements
that are in the set, and then how many elements are in each
permutation. When you start thinking about this with a wider scale
than what the assignment really calls for, you can see more solutions
than are normally apparent.

Cheers.

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

In discrete mathematics, the number of permutations of a group without
repetition is the (total number of elements)Factorial divided by [(the
total number of elements) - (the number you can choose each time)]

for example, the number of telephone numbers you can have is P(10, 4),

or

10!/(10 - 4)! = 5040 phone numbers.
if you perform this test at the start of the program, then you would
know how many permutations you would need. With permutations, you
can't really do it recursivly, as it is often you could be hit with an
infinate set, like the integers. If you can write a program that could
produce all the permutations of the set of the integers crossed with
the set of the integers, you would need one phat computer to do that.

In order to make this program as scalable as possible, you must create
a function (or method, ive been programming c so long i think i have
gone to the dark side) that could take the input of how many elements
that are in the set, and then how many elements are in each
permutation.

But this is does not solve the original posters problem, since the
elements in the permutations are chosen from different sets (I'm not
sure it is mathematically correct to call them permutations though.)

To solve the problem you brought up, something different is needed. It
is not enough to know how many elements there are in the set, you must
also know what the elements are. So the input would be the set and the
number of elements in a permutation. Of the top of my head, it could be
solved by removing elements from the set once they are used, and once
they are no longer in use they are put back.