Permutation of string limited by another string

I'm having a bit of trouble, mainly because I do not have much experience with recursive methods and a non-recursive method for my problem seems incredibly complex. However, I might just be looking at this the wrong way.

What I'm trying to accomplish is this:

Given one string, I want to overlap them and display all potential combinations. It's probably easiest if I explain my problem and solution with binary representations.

Given 0000 and 1111,

I want my method to return:

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

This seems incredibly trivial, but I just ca开发者_C百科n't seem to figure out the most efficient way of doing this. I was thinking either recursion or maybe a binary tree. Either way, I'm having trouble setting it up.

Any ideas would be greatly appreciated.

Thank you!

Poor, but passable iterative approach.

import java.util.BitSet;

public class p {

   static StringBuilder sb;

   // Add one and return true on overflow
   static boolean inc( BitSet s, int maxlen ) {

      int i = 0;
      for( ; i < maxlen; ++i ) {

         if( s.get( i )) { s.clear( i ); }
         else            { break; }
      }

      if( i == maxlen )
         return true;

      s.set( i );
      return false;
   }

   static String form( String x, String y, BitSet mask ) {

      sb.setLength( 0 );
      for( int i = 0; i < x.length(); ++i )
         sb.append( (mask.get( x.length() - i - 1) ? y : x).charAt( i ));

      return sb.toString();
   }

   public static void perms( String x, String y ) {

      assert( x.length() == y.length() );

      BitSet bits = new BitSet( x.length() );

      do {
         System.out.println( form( x, y, bits ));
      } while( ! inc( bits, x.length() ));
   }


   public static void main( String[] args ) {

      sb = new StringBuilder( args[0].length() );
      perms( args[0], args[1] );
   }
}

Your binary explanation actually gave me a very good idea for doing this. You can simply use a for loop and increment the variable until it is 2 ^ str.Length * 2 - 1. In each iteration, one permutation is the characters from the first string where the corresponding bit in the variable is 0, or from the second string where it is 1. Pseudo-code:

for i = 0 to 2 ^ string1.length * 2 - 1
    s = ""
    for j = 0 to string1.length - 1
        if (i >> j) & 1 == 1 then
            s = string1[string1.length - j] + s
        else
            s = string2[string2.length - j] + s
        end if
    end for
end for

You want this:

/*************************************************************************
 *  Compilation:  javac Permutations.java
 *  Execution:    java Permutations N
 *  
 *  Enumerates all permutations on N elements.
 *  Two different approaches are included.
 *
 *  % java Permutations 3
 *  abc
 *  acb
 *  bac 
 *  bca
 *  cab
 *  cba
 *
 *************************************************************************/

public class Permutations {

    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s) { perm1("", s); }
    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0) System.out.println(prefix);
        else {
            for (int i = 0; i < N; i++)
               perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s) {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n) {
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j) {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }



    public static void main(String[] args) {
       int N = Integer.parseInt(args[0]);
       String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
       String elements = alphabet.substring(0, N);
       perm1(elements);
       System.out.println();
       perm2(elements);
    }
}

Just for laughs, a very inefficient recursive solution:

import java.util.ArrayList;

public class pp {

   static ArrayList<String> append(
      String x, String y, ArrayList<String> ss ) {

      if( x.length() == 0 )
         return ss;

      ArrayList<String> r = new ArrayList<String>( ss.size() * 2);
      for( int i = 0; i < ss.size(); ++i ) {
         r.add( ss.get( i ) + x.charAt( 0 ));
         r.add( ss.get( i ) + y.charAt( 0 ));
      }

      return append( x.substring(1), y.substring(1), r );
   }

   public static void main( String[] args ) {

      assert args[0].length() == args[1].length();

      ArrayList<String> ss = new ArrayList<String>( 1 );
      ss.add( "" );

      ArrayList<String> r = append( args[0], args[1], ss );
      for( int i = 0; i < r.size(); ++i )
         System.out.println( r.get( i ));
   }
}