CODEWITHSUNDEEP
javaarrays
Chandrasekhar Gontla
Chandrasekhar Gontla

Reputation: 13

Print all possible combinations for a given array of elements

public class TestPossibleNumbers {
public static void main(String[] args) {
    int input[] = { 1, 2, 3 };
    // int input[] = {10,11,12,13};
    possibleNumbers(input, 0);
}

public static void possibleNumbers(int[] x, int index) {
    if (index == x.length) {
        for (int i = 0; i < x.length; i++) {
            System.out.print(x[i] + " ");
        }
        System.out.println();
    }
    for (int i = index; i < x.length; i++) {
        int temp = x[index];
        x[index] = x[i];
        x[i] = temp;
        possibleNumbers(x, index + 1);

        temp = x[index];
        x[index] = x[i];
        x[i] = temp;
    }
}}

Can anyone help me to understand the code inside for loop? This program run perfectly. But, I am unable to figure out how it is working

Upvotes: 1

Views: 9511

Answers (3)

Guhan Nagarajan
Guhan Nagarajan

Reputation: 51

The Program prints permutation of numbers not combination.

Permutation - Order matters Combination - Order doesnt matter and more of choosing k elements out of n

for example 

int a= {a,b};
permutation = {ab,ba} 
whereas combination ={{},{a},{b},{a,b}}

To understand how the program works go through the following link will https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Don't get confused on recursion inside for loop. if (index == x.length) is the terminating condition for recursion. Inside the for loop before and after calling the recursive call possibleNumberselements are swapped.

Before swap helps to generate all possible outcomes and after swap elements will swap to previous position so that all other permutation will be generated from the for loop. It may sounds confusing please go through the link.

Upvotes: 0

sprinter
sprinter

Reputation: 27986

I'll provide an alternative explanation that I feel is more intuitive.

Consider the case of only 1 number in the list: [a]. This is pretty trivial: there's a single combination [a].

Now consider the case of 2 numbers in the list: [a, b]. In this case you can take each of the elements in turn and then look at all combinations of the remaining element using the previous method and then add the element back.

Now consider the case of 3 numbers in the list: [a, b, c]. In this case you can take each of the elements in turn and then look at all combinations of the other 2 elements using the previous method and then add the element back.

And so on for 3, 4, 5... elements.

So, in general, consider the case of n numbers in the list: [a1, a2, ... an]. In this case take each of the elements in turn and then look at all combinations of the other n-1 elements using the exact same method and then add the element back.

Converting to pseudo code:

getCombos(values)
    for each value
        for each combo in getCombos(values with value removed)
            add value + combo to results
    return results

The only thing to add is the base case which is necessary for all recursive implementations. One possibility is the case of a single item. However there's an even simpler one: if there are no values then the result is a single empty list.

So converting that to Java, using sets to make clear that the elements need to be unique (to avoid duplicate results), using streams and making it generic so it'll work for any type:

Stream<List<C>> combos(Set<C> values) {
    if (values.isEmpty())
        return Stream.of(new ArrayList<>());
    else
        return values.stream().flatMap(value -> 
            combos(values.stream()
                .filter(v -> !v.equals(value))
                .collect(toSet())).peek(r -> r.add(value)));
}

Your code is really just an alternate implementation of the same algorithm that swaps the element under consideration to the front of the array instead of creating a new collection.

Upvotes: 0

alikhtag
alikhtag

Reputation: 326

You are recursively calling the method again at:

 possibleNumbers(x, index + 1);

Thus the method runs the method again, with index + 1 passed. It checks if 

if(index == x.length)

If the statement is correct it prints the numbers.

It then enters the 2nd for loop again(if the if statement was incorrect it will still enter it). And calls the recurring method again. It will keep entering 2nd for loop but when "index" will be equal to or greater than "i.length" no iterations of the for loop will run because you specified for loop to run only when:

 i<i.length

When 2 for loop does not do any iterations the method will stop recurring. So in your case when index is equal to 3 no iterations of 2nd for loop will run.

Try running debug step by step to see what is happening more in depth.

Upvotes: 1

Related Questions