Removing an input from a recursive method

Question

Good morning! I received a problem statement to write a method that returns all possible combinations of a String input passed, e.g.

if ABC is passed then it returns [A, AB, BC, ABC, AC, B, C] if ABCD is passed then it returns [A, AB, BC, CD, ABC, AC, ACD, B, BCD, BD, ABD, AD, C, D, ABCD]

means AB and BA are always taken same, ABC, BAC and ACB are also same.

I ended up writing below code and it seems to working though (not sure).

public static Set<String> getAnyPermutations(String s,String strInput) {
    Set<String> resultSet = new HashSet<>();
    char[] inp = strInput.toCharArray();
    for(int i=0; i<inp.length; i++) {
        String temp =s+String.valueOf(inp[i]);
        resultSet.add(temp);
        if(i+1<=inp.length)
            resultSet.addAll(getAnyPermutations(temp, String.valueOf(Arrays.copyOfRange(inp, i+1, inp.length))));
    }
    return resultSet; 
}

My question is, I want to remove the first param(String s) from the method as using it for interal comutations only, or if that is not possible then making sure that user always pass a "" value or I can reset it to "" for the first(non-recursive) call of this method. I am going confused how to do that inside a recursive funtion. Also please add comment if you have doubt it can fail other than this situation.

Conditions, All has to be done inside this function only, no other method can be created.

"no other function can be created" - why not? Extract-method is often a very good refactoring. — slim, Aug 14 '17 at 13:07

score 4 · Answer 1 · answered Aug 14 '17 at 12:57

All has to be done inside this function only, no other function can be created.

Then you can't do it. The function has no (reasonable)* way of knowing whether it called itself or was called by another function.

There are lots of solutions involving creating another function. One that might fit your requirements, depending on how they're actually expressed, would be to have the function define a lambda to do the work, and have the lambda call itself. E.g., getAnyPermutations wouldn't actually be recursive, it would contain a recursive function.

But that may be out of bounds depending on the exact meaning of the quote above, since the lambda is another function, just not one that can be accessed from the outside.

* The unreasonable way is by examining a stack trace, which you can get from Thread.currentThread().getStackTrace.

score 2 · Answer 2 · answered Aug 14 '17 at 13:08

You can change the current method to be a private one and interface it with a public method with one argument e.g.:

private static Set<String> getAnyPermutations(String s,String strInput) {
    Set<String> resultSet = new HashSet<>();
    char[] inp = strInput.toCharArray();
    for(int i=0; i<inp.length; i++){
        String temp =s+String.valueOf(inp[i]);
        resultSet.add(temp);
        if(i+1<=inp.length)
            resultSet.addAll(getAnyPermutations(temp, String.valueOf(Arrays.copyOfRange(inp, i+1, inp.length))));
    }
    return resultSet; 
}

Now, you can expose a one argument method to the user which in turn will call the above method, e.g.:

public static Set<String> getAnyPermutations(String strInput) {
    return getAnyPermutations("", strInput);
}

Update

If you can't create any other method at all then the only alternative would be to use var-args. However, that requires change in the implementation and doesn't actually restrict the user from passing multiple values.

slim · Answer 3 · 2017-08-14T14:36:21.930

You can rewrite this particular algorithm so that it doesn't need to carry a state through to the recursively called invocation.

(Java-centric pseudocode):

Set<String> getAnyPermutations(String str) {
    if(str.length() == 0) {
        return Collections.emptySet();
    }

    String head = str.substring(0,1);
    String tail = str.substring(1);

    Set<String> permutationsOfTail = getAnyPermutations(tail);

    Set<String> result = new HashSet();

    // Head on its own
    // For input 'ABC', adds 'A'
    result.add(head);

    // All permutations that do not contain head
    // For input 'ABC', adds 'B', 'C', 'BC'
    result.addAll(permutationsOfTail);

    // All permutations that contain head along with some other elements
    // For input 'ABC', adds 'AB, 'AC', 'ABC'
    for(String tailPerm : permutationsOfTail) {
       result.add(head + tailPerm);
    }

    return result;
}

This meets your aim of not creating any extra methods -- but note that it would be cleaner code if the for loop was extracted into a new method Set<String> prefixEachMember(String prefix, Set<String> strings) allowing result.addAll(prefixEachMember(head,permutationsOfTail)).

However it's not always possible to do this, and sometimes you do want to carry state. One way is the way you've asked to avoid, but I'm going to include it in my answer because it's a clean and common way of achieving the aim.

 public Foo myMethod(Bar input) {
      return myMethod(new HashSet<Baz>(), input);
 }

 private Foo myMethod(Set<Baz> state, Bar input) {
      if(...) {
          return ...;
      } else {
          ...
          return myMethod(..., ...); 
      }
 }

Here, the first method is your public API, in which the collector/state parameter is not required. The second method is a private worker method, which you initially call with an empty state object.

Another option is to refer to an object field. I would recommend against this, however, because it gets confusing when recursive code refers to a global object.

If instead of `return Collections.emptySet();` you `return Collections.singleton("")`, you can omit the `result.add(head);` as it becomes part of the loop. And of its own, I'd regard the 1-element set containing the empty string as correct solution to the empty-string input case. — Ralf Kleberhoff, Aug 14 '17 at 14:34
@RalfKleberhoff well, I guess OP can decide their requirement. I would say that the correct output for an empty string, is an empty set. — slim, Aug 14 '17 at 14:37
Correct. I didn't read the OP statement carefully. There is no empty string in the reference results the OP gave us. That rules out my modification to your answer.. — Ralf Kleberhoff, Aug 14 '17 at 14:46

score 2 · Accepted Answer · answered Aug 14 '17 at 14:26

You can always transform a recursive method into its iterative equivalent - e.g. see Way to go from recursion to iteration.

In the iterative version it's easy to not expose the state parameter (you now just need to initialize it at the beginning of the iterative method).

This is not very practical in general (but I believe that the purpose of the question is more theoretical, otherwise it's always a good solution to just expose another method).

Furthermore, in this particular situation you might consider this simple iterative approach (though it is not obtained by directly translating the given code):

public static Set<String> getAnyPermutations(String strInput) {
    Set<String> resultSet = new HashSet<>();
    char[] inp = strInput.toCharArray();

    for (int bitMask = 0; bitMask < (1 << inp.length); bitMask++) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < inp.length; i++) {
            if ((bitMask & (1 << i)) != 0) {
                str.append(inp[i]);
            }
        }

        if (str.length() > 0) {
            resultSet.add(str.toString());
        }
    }

    return resultSet;
}

this is awesome and works amazingly.. but I dont understand how can someone think this solution..how did you break down the problem and these bitwise shifts, are you expert in those or is there any way to think in that direction? Many Thanks! — Vikash, Aug 14 '17 at 15:42
It is a known technique for iteratively generating all the subsets of a set of size N. See for example this link: https://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set/12588460#12588460 — danbanica, Aug 14 '17 at 15:46

Removing an input from a recursive method

4 Answers4