# Thread: Recursion with arrays

1. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Recursion with arrays

Hello all. I'm trying to make a method to loop a method to make 6 numbers from an arraylist interact with eachother. These 6 numbers will interact with eachother through other methods with addition, subtraction, multiplication and division. I need to implement other methods where the position is important (for division, ie 2/3 =/= 3/2).

I'll try to make my intention as clear as possible:
I have an array of 6 integers which are defined when the class is initialized. However each of the elements of the array need a way to interact with another element and each element can only be used once for one chain of recursion. So when I'm recursing through the array, the element on position 2 in the array cannot be used twice for example. During the iteration something must be done and checked, but that shouldn't be a problem (it's another part of the code that's dependant on but not necessary for the recursion itself). The tricky part is that the position of the element matters which means everything must be done all over, but in different orders.

To illustrate, i'll use the numbers as elements:
1 -> 2 -> 3 -> 4 -> 5 -> 6 // I just had a chain of going through all the elements in that order.
1 -> 2 -> 3 -> 4 -> 6 -> 5
1 -> 2 -> 3 -> 5 -> 4 -> 6
1 -> 2 -> 3 -> 5 -> 6 -> 4
1 -> 2 -> 3 -> 6 -> 4 -> 5
1 -> 2 -> 3 -> 6 -> 5 -> 4
...
2 -> ... (element 1 must now be available for the rest of this recursion chain, but not 2 since it is already used once for this chain.)

I hope I clarified what I am trying to do well enough.

Here's some code I tried that I thought would work:

//getIntegers() was returning an arraylist of these 6 numbers, but I changed it to an array, though
// this code is still working with the arraylist. If needed I could put the elements in the array
// in an array list instead. This method initializes the recursion with initial arraylist and element.
public void calculate(){
calculateRecursion(getIntegers(), getIntegers()[0]);
}

/**
* Goes through every single combination of integers with all the possible
* interactions.
*/
private void calculateRecursion(ArrayList<Integer> givenArraylist, int sum){
int totalSum = sum;
ArrayList<Integer> localList = givenArraylist;
for(int i = 0; i < localArraylist.size(); ){
ArrayList<Integer> whileList = localList;
whileList.remove(0);
calculateRecursion(whileList, totalSum);
}
}
My reasoning for this last method was to store the arraylist given as input in the method in localList, go through the elements and subtract the current (first) element. That way each element will be used only once, and when the recursion goes back previous local arraylists will be restored. What I did not realize is that apparently the local arraylist seems to be working the same for each recursion, meaning there won't be a new arraylist defined for each recursion?

What I wanted was to have the elements from 1 -> 2 -> ... -> 6, go to 1 > 2 -> .. -> 5 -> 6 and so on, but it stops after the first time it reaches all 6 elements cause the arraylists will be empty, and not restored to the level of recursion when the recursion goes a few steps back.

Any help would be greatly appreciated (maybe there's another, easier way to handle this maybe? I'm not at all dead set on using arrays or array lists).
Last edited by bibliotheek357; 09-17-2011 at 05:07 AM. Reason: Tabs and spaces don't seem to work, so i've made the illustration more clear.

2. ## Re: Recursion with arrays

You don't need recursion for that; you want all permutations of those six numbers; it can be nicely done iteratively. Let P == p(0), p(1), p(2) ... p(n) be a current permution; you can find the next permutaion in lexicographical order (if any) as follows:

1) find the largst i such that p(i) < p(i+1); if you can't find such I you have already found the last permutation, so stop;
2) find the largest j > i such that p(j) > p(i); note that such j always exists;
3) swap elements p(i) and p(j);
4) reverse the entire sequence p(i+1), p(i+2) ... p(n).

Repeat the four steps above until step 1) fails. Try it with a piece of paper and a pencil before you start coding.

kind regards,

Jos

3. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

Thank you for your fast respons JosAh! (I was asleep however ^^;) I can see your point for the most part in using permutations. But I'm not sure I can completely follow your steps, especially the fourth one. Basically for the first 3 steps I will first go through 1 to 5, then stop there because there is no 7th element, then j = 6, and I will switch i = 5 with j = 6. Then I'm stuck on what should happen here. Reverse the entire sequence? i+1 would be 6 at the moment, so the order should be 6->1->2->...->5 at this point? I don't understand what I should do with this new ordering.

EDIT: I found this site that pretty much does what you suggested. (the perm2 and swap methods)
http://introcs.cs.princeton.edu/java...ions.java.html

I don't recognize the fourth step in this example, but it gives me a bit more of a clear view on how to approach this.
Last edited by bibliotheek357; 09-17-2011 at 03:07 PM. Reason: Now that I've read through your post a few more times I might have interpretted your first step wrong aswell..

4. ## Re: Recursion with arrays

Originally Posted by bibliotheek357
Thank you for your fast respons JosAh! (I was asleep however ^^;) I can see your point for the most part in using permutations. But I'm not sure I can completely follow your steps, especially the fourth one. Basically for the first 3 steps I will first go through 1 to 5, then stop there because there is no 7th element, then j = 6, and I will switch i = 5 with j = 6. Then I'm stuck on what should happen here. Reverse the entire sequence? i+1 would be 6 at the moment, so the order should be 6->1->2->...->5 at this point? I don't understand what I should do with this new ordering.
For example, let a current permutation be "abdec"; the steps run as follows:

1) i= 2, because d < e;
2) j= 3, because e > d;
3) swap p(i) and p(j): abedc;
4) reverse sequence p(3), p(4): result:abecd.

So the next permutation is abecd.

kind regards,

Jos

5. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

I'm finally starting to get the hang of it a bit. It's not completely working yet but I seem to be getting there. However I've stumbled on something I should've noticed sooner.. I am planning to make these 6 numbers either add, subtract, multiply or divide by eachother. And during each step I'm checking whether that result is the number I'm looking for. So I could do (element 1 + element 4) / element 3 == goal number? This means that during the permutation's, I'm doing yet another permutation between 4 operatives.. Are there ways to simplify this? It's getting a little bit over my head.

6. ## Re: Recursion with arrays

Can you tell us what it is what you want exaclty? Leave out the techinicalities such as recursion etc. You have six numbers and a goal number; right? You want to find/create an expression with those six numbers and a few operators such that the expression (after being being evaluated) equals that goal number; right?

kind regards,

Jos

7. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

Alright, so it's a small minigame that I'm trying to make. What this program does is find out all the answers for a given game. I have 6 numbers and a goal number and these 6 numbers must be numbers [1, 10], 25, 50, 75 and 100. I already have a method that checks if the given input follows this condition. The goal number is a number in the [100,999] interval. The point of this game is to use any combination of those 6 numbers, using only addition, subtraction, multiplication and division to reach that goal number. Each number can only be used once, but not all numbers must be used. So to reach 109 with the numbers 25, 7, 9, 6, 10 and 100; we can simply add 100+9, or (9x10)+25-6, or ...

So you are basically correct in guessing what I'm trying to do.

In the context of the method I'm trying to work out, I'm trying to find all the possible combinations between these 6 numbers that can add, subtract etc, while checking during each step if the goal number has been found. It is my intention to store all the possible ways to reach this goal, meaning I also need a way to remember through which elements and what operation I used to achieve the answer.
Last edited by bibliotheek357; 09-17-2011 at 05:41 PM.

8. ## Re: Recursion with arrays

Enumerating expressions is a tedious job; it is far easier to enumerate them in postfix form; e.g. the expression (3+4)*2 is written in postfix form as 3 4 + 2 *. In general, if n is (any) number and o any valid operator then any string of n's and o's can represent a postfix expression. e.g. the postfix expression above can be repesented as nnono; not all strings of n's and o's are valid postfix expressions but that can easily be checked.

As an aside, the permutation algorithm I described above can also handle duplicates, e.g. when you feed it the sequence aab, it'll generate the permutations aab, aba and baa. Given a string of n's and o's it can generate all permutations of it. If you have six numbers, you should have five operators to form a valid expression in postfix form; note that not all of them are valid expressions in postfix form though, e.g. oonnn isn't a valid postfix form expression.

The 'trick' is to generate all permutations of 6 n's and 5 o's and check if they make up a valid expression in postfix form and if it equals your goal number. Just for fun I implemented this scenario and it works. I leave it up to you to also implement this ;-)

kind regards,

Jos
Last edited by JosAH; 09-17-2011 at 07:04 PM.

9. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

That sounds like a pretty good idea! :P Thanks for the help Jos, I appreciate it a lot. I will definately get to it and post here when I stumble on another problem/found a solution.

10. ## Re: Recursion with arrays

Originally Posted by bibliotheek357
That sounds like a pretty good idea! :P Thanks for the help Jos, I appreciate it a lot. I will definately get to it and post here when I stumble on another problem/found a solution.
Good; post your solution here so we can see it (and I can compare it to my solution ;-)

kind regards,

Jos
Last edited by JosAH; 09-17-2011 at 07:27 PM.

11. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

It's been two days since I last posted, but I definately didn't forget or dropped the project. In fact, I finally got it completed. :D It took me alot longer than expected, though it's still vacation after all. :) I had to refresh some knowledge which I had lost and gained some new knowledge xd I have uploaded my jar-file in the link below (note to click the blue download button, not the green one..):

If the link or jar-file doesn't work for whatever reason I can copy paste the code here aswell. I am pretty sure my code is not very optimal as I was not able to do it as you suggested afterall (using the arrangements of operators and integers as permutations). I'd like to hear from your opinion on how I could have improved my code or do it otherwise (maybe give an example on how to include the permutations for the operators and integers?).

Also, to get back to the link I posted earlier:
Permutations.java

Does anyone have an idea what the idea behind the second method is? The first perm2 simply breaks the string down to individual characters. However the algorithm in the second perm2 method is so seemingly random, but it seems to work. Does anyone have an idea what algorithm this is based on? I have checked the method and it did work, but I don't really like to use methods I don't understand the mechanism of.

12. ## Re: Recursion with arrays

I can't open the jar file; can you post your code here please? About the second permutation method: given a sequence of n characters, swap the i-th and last character and recursively find all permutations of n-1 characters. If you do that for each character in the sequence you found all permutations (not in lexicographical order) because you have moved each character to every possible position.(try it out by hand).

kind regards,

Jos

13. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

Aah alright, I get it!

I'll just copy paste my code here:
Java Code:
```import java.util.ArrayList;
import java.util.Arrays;

public class Calculation {

public Calculation(int a, int b, int c, int d, int e, int f, int goal){
initializeValidStarters();
setGoal(goal);
setIntegers(a, b, c, d, e, f);
}

private void initializeValidStarters(){
for(int i = 1; i <= 10; i++){
}
}

private void setIntegers(int a, int b, int c, int d, int e, int f)
throws InvalidStartingIntegerException{
integers[0] = a;
integers[1] = b;
integers[2] = c;
integers[3] = d;
integers[4] = e;
integers[5] = f;
if(!validStartingIntegers()){
throw new InvalidStartingIntegerException("Invalid input integer.");
}
}

public int[] getIntegers(){
return integers;
}

private int[] integers = new int[6];

public boolean goalReached(int z){
return (z == getGoal());
}

private void setGoal(int goal)
throws InvalidStartingIntegerException{
if(validGoal(goal)){
goalNumber = goal;
}
else throw new InvalidStartingIntegerException("Invalid input goal");
}

public boolean validGoal(int goal){
if((goal >= 100) && (goal <= 999)){
return true;
}
else return false;
}

public int getGoal(){
return goalNumber;
}

private int goalNumber;

public boolean validStartingIntegers(){
for(int i = 0; i < 6; i++){
if(!list.contains(getIntegers()[i])){
return false;
}
}
return true;
}

/**
* The array must be sorted from small integers to large integers first.
*/
public void calculate(){
Arrays.sort(getIntegers());
System.out.println("Goal number: " + getGoal());
System.out.println();
//displayArray(getIntegers());
checkSolution(getIntegers(), getIntegers()[0], 0, new ArrayList<Integer>());
permutatePossibilities(getIntegers());
}

/**
* Goes through every single combination of integers with all the possible
* interactions.
*
* Find operator after a permutation has been found?  Or permutate operators directly?
*/
private void permutatePossibilities(int[] givenArray){
for(int i = givenArray.length-2; i >= 0; i--){
if(givenArray[i] < givenArray[i+1]){
for(int j = givenArray.length-1; j > i; j--){
if(givenArray[i] < givenArray[j]){
swap(givenArray, i, j);
reverseSequence(givenArray, i+1, givenArray.length-1);
//displayArray(givenArray);
checkSolution(givenArray, givenArray[0], 0, new ArrayList<Integer>());
permutatePossibilities(givenArray);
break;
}
}
break;
}
}
}

private void displayArray(int[] array){
for(int i = 0; i < array.length; i++){
System.out.print(array[i] + " ");
}
System.out.println();
}

private void swap(int[] a, int i, int j) {
int c;
c = a[i]; a[i] = a[j]; a[j] = c;
}

private void reverseSequence(int[] a, int j, int n){
for (int i = j; i < n; i++)
{
swap(a, i, n--);
}
}

public void checkSolution(int[] a, int result, int i, ArrayList<Integer> operators){
i += 1;
if(goalReached(result)){
displayUsedIntegers(a, i, operators);
return;
}
while(i < a.length){
for(int z = 0; z < 4; z++){
result = doOperator(result, a[i], z);
checkSolution(a, result, i, operators);
//reverse the operator to give the result its original number back.
operators.remove(operators.size()-1);
if((z == 2) && !isDivided(result, a[i])){
continue;
}
result = doOperator(result, a[i], 3-z);
}
break;
}
}

private boolean isDivided(int x, int y){
if(division(x, y) == x){
return false;
}
else return true;
}

private void displayUsedIntegers(int[] a, int j, ArrayList<Integer> operators){
System.out.print("Combinatie oplossing: ");
for(int k = 1; k < j; k++){
System.out.print("(");
}
for(int i = 0; i < j; i++){
System.out.print(a[i]);
if(i > 0){
System.out.print(")");
}
System.out.print(" ");
if(i < (j-1)){
System.out.print(displayOperator(operators.get(i)) + " ");
}

}
System.out.println();
}

private String displayOperator(int z){
if(z == 0){
return "+";
}
if(z == 3){
return "-";
}
if(z == 1){
return "*";
}
if(z == 2){
return "/";
}
return null;
}

public int doOperator(int x, int y, int z){
if(z == 0){
}
if(z == 3){
return subtraction(x, y);
}
if(z == 1){
return multiplication(x, y);
}
if(z == 2){
return division(x, y);
}
// random 0 gegeven, maar beter exception gebruiken
else return 0;
}

public int addition(int x, int y){
return (x+y);
}

public int subtraction(int x, int y){
return (x-y);
}

public int multiplication(int x, int y){
return (x*y);
}

/**
* Returns x if the division divides by zero, or if the resulting division is not
* an integer.  Returns x/y otherwise.
*/
public int division(int x, int y){
if(divideByZero(y) || !isDivisionResultInteger(x, y)){
return x;
}
else return (x/y);
}

public boolean divideByZero(int y){
if(y == 0){
return true;
}
else return false;
}

public boolean isDivisionResultInteger(int x, int y){
int z = x%y;
if(z == 0){
return true;
}
else return false;
}

public ArrayList<Integer> getList(){
return list;
}

ArrayList<Integer> list = new ArrayList<Integer>();

}```

in a different class called start, i run the main method:

public static void main(String[] args) {
calculation = new Calculation(2, 3, 7, 9, 50, 100, 971);
calculation.calculate();
}

You fill in the 6 numbers you like for the first 6 integers (must be a valid integer, belonging to {[1,10], 25, 50, 75, 100}). The last number is the goal number and must be within [100,999].

I am currently also working out a method to check whether there are any input that would have no solutions.
Last edited by JosAH; 09-20-2011 at 08:48 PM. Reason: added [code] ... [/code] tags

14. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

Of course you need to add
private static Calculation calculation;
to the start class. :P

15. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

I am already encountering difficulties in finding problems with no solutions.. Just to clarify what my current objectives are, I am trying to find all the problems (any valid input combinations) that would have no solutions and print them out. An example would be 1,2,3,4,5,6,100; which is of course not correct since it can in fact be solved. (for example (4*5)*(6-1) = 100)

I recognize I will use alot of the methods that I already have so I made a subclass of the above class, Calculation, called NoSolutions. I would then like to permutate these 13 integers ([1,10], 25,50,75,100 of which I will insert 6 in the Calculation class. If there is any output, meaning a solution has been found, it should continue to the next permutation and so on, saving any combinations that didn't have a solution. This shouldn't be too hard to implement, but the difficulty lies in choosing the 6 numbers from the pool of 13 numbers. If I were to use the above permutation I would get alot of doubles, like
1,2,3,4,5,6,7,8,9,10,25,50,75,100
1,2,3,4,5,6,7,8,9,10,25,50,100,75
and so on, when I am only interested in the difference in the first 6 of every permutation. Any ideas on how to permutate for the first 6 numbers in an array(list) of 13 numbers, without getting those clones?

16. ## Re: Recursion with arrays

Well done; I took a bit different approach: let a 1 bit denote an operator an let a 0 bit denote an operand. A sequence of bits denotes a postfix expression; for that expression to be ok it needs to contain n 0 bits and n-1 1 bits (one operator less than there are numbers. If we have to check 6 numbers there must be 5 one bits in the 11 bit bitsequence. Checking that is easy, so all I have to do is enumerate from 0 to 1<<11, check if the bitsequence contains 5 one bits and check the postfix expression afterwards and see if it equals the goal. Checking the postfix expression isn't difficult either: if a bit in the bitsequence is 1 I enumerate the four operators: + - * and /. if the bit is a zero I pick one of the available numbers. Because not all postfix expressions are unique I collect the possible solutions in a Set to keep the unique ones. This is my code:

Java Code:
```import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class Exprs {

private static boolean[] used;
private static int[] numbers;
private static Stack<Integer> s= new Stack<Integer>();
private static Stack<String> r= new Stack<String>();
private static Set<String> result= new TreeSet<String>();

private static int count(int x) {

int c;

for (c= 0; x != 0; x&= x-1, c++);

return c;
}

private static void push(int v, String sv) { s.push(v); r.push(sv); }
private static void pop() { s.pop(); r.pop(); }

private static void evalNumber(int p, int n, int goal) {
for (int j= 0; j < used.length; j++)
if (!used[j]) {
push(numbers[j], ""+numbers[j]);
used[j]= true;
eval(p>>1, n-1, goal);
used[j]= false;
pop();
}
}

private static void evalOperator(int p, int n, int goal) {

if (s.size() < 2) return;

int b= s.pop();
int a= s.pop();
for (int j= 0; j < 4; j++) {
switch (j) {
case 0:
push(a+b, "+");
eval(p>>1, n-1, goal);
pop();
break;

case 1:
push(a-b, "-");
eval(p>>1, n-1, goal);
pop();
break;

case 2:
push(a*b, "*");
eval(p>>1, n-1, goal);
pop();
break;

case 3:
if (b != 0 && a%b == 0) {
push(a/b, "/");
eval(p>>1, n-1, goal);
pop();
}
break;
}
}
s.push(a);
s.push(b);
}

private static void eval(int p, int n, int goal) {

if (s.size() == 1 && s.peek() == goal)
else if (n > 0) {
if ((p&1) == 0)
evalNumber(p, n, goal);
else
evalOperator(p, n, goal);
}
}

public static void main(String[] args) {

numbers= new int[] { 1, 2, 3, 4 }; // just for testing
used= new boolean[numbers.length];

for (int p= 0; p < 1<<(2*numbers.length-1); p++)
if (count(p) == numbers.length-1)
eval(p, 2*numbers.length-1, 10); // can we make 10 out of the numbers?

for (String r : result)
System.out.println(r);
}
}```
kind regards,

Jos

17. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

I understand most of what you did. (Pretty amazing how you wrote in so little code what took me 2 pages to write..) However I'm not familiar with the >> expression. What does it mean if you use 'p>>1'? It seems to be an integer, but I can't extract the meaning out of the context.

18. ## Re: Recursion with arrays

Originally Posted by bibliotheek357
I understand most of what you did. (Pretty amazing how you wrote in so little code what took me 2 pages to write..) However I'm not familiar with the >> expression. What does it mean if you use 'p>>1'? It seems to be an integer, but I can't extract the meaning out of the context.
>> is the shift-right operator; for any ints a and b, a >>b moves (shifts) all bits of a, b positions to the right. e.g. (in binary) 1011001 >> 2 == 10110; the rightmost b bits are lost in the result.

kind regards,

Jos

19. Member
Join Date
Sep 2011
Posts
11
Rep Power
0

## Re: Recursion with arrays

Aah alright, I understand! Thank you very much, the clever use of set and stack has been an inspiration on my question in the post directly above your solution aswell. So all I have to do is save my solutions in a set and those doubles will not appear. The difference between a novice and an expert is pretty big :P

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•