Display Possible Combinations of String

Generating all permutations of a given string

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction to Programming in Java)

Display possible combinations of string

Set two iterators and print everything between them. So something like this:

<?
$str = "How are you";
$words = explode(" ",$str);
$num_words = count($words);
for ($i = 0; $i < $num_words; $i++) {
  for ($j = $i; $j < $num_words; $j++) {
    for ($k = $i; $k <= $j; $k++) {
       print $words[$k] . " ";
    }
    print "\n";
  }
}
?>

Output

---

How 
How are 
How are you 
are 
are you 
you 

How to generate all possible combinations?

Try this.

The general algorithm is to have a fromList containing the letters you haven't used yet and a toList that is the string you've built up so far. This uses recursion to build up all possible strings and adds them to the set when the length is 2 or greater:

func permute(fromList: [String], toList: [String] = [String](), var set: Set<String> = Set<String>()) -> Set<String> {
    if toList.count >= 2 {
        set.insert(toList.joinWithSeparator(""))
    }
    if !fromList.isEmpty {
        for (index, item) in fromList.enumerate() {
            var newFrom = fromList
            newFrom.removeAtIndex(index)
            set = permute(newFrom, toList: toList + [item], set: set)
        }
    }
    return set
}

permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}

permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}

---

Faster Answer:

As @MartinR pointed out in his post, the solution above is a little slow because of all of the creation and copying of sets. I had originally written this using an inout variable for set, but changed it to the more functional interface to make it nice to call.

Here is my original (faster) implementation, plus I embedded it in a permute that takes just an [String] and returns a Set<String>. It does the work of creating the set and the toList array and then calls the inner version of permute to do the real work:

func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
    func permute(fromList: [String], toList: [String], minStringLen: Int, inout set: Set<String>) {
        if toList.count >= minStringLen {
            set.insert(toList.joinWithSeparator(""))
        }
        if !fromList.isEmpty {
            for (index, item) in fromList.enumerate() {
                var newFrom = fromList
                newFrom.removeAtIndex(index)
                permute(newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
            }
        }
    }

    var set = Set<String>()
    permute(list, toList:[], minStringLen: minStringLen, set: &set)
    return set
}

permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}

permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}

permute(["A", "A", "B"], minStringLen: 1)
// {"BA", "A", "BAA", "AB", "AA", "B", "AAB", "ABA"}

permute(["A", "A", "B"], minStringLen: 3)
// {"ABA", "BAA", "AAB"}

Edit:
I added a minStringLen parameter (with default value of 2) instead of hard coding that value.

See @MartinR's answer for performance comparisons.

---

Swift 3 and Swift 4:

func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
    func permute(fromList: [String], toList: [String], minStringLen: Int, set: inout Set<String>) {
        if toList.count >= minStringLen {
            set.insert(toList.joined(separator: ""))
        }
        if !fromList.isEmpty {
            for (index, item) in fromList.enumerated() {
                var newFrom = fromList
                newFrom.remove(at: index)
                permute(fromList: newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
            }
        }
    }

    var set = Set<String>()
    permute(fromList: list, toList:[], minStringLen: minStringLen, set: &set)
    return set
}

print(permute(list: ["A", "B", "C"]))
// ["ABC", "CA", "BAC", "ACB", "BA", "CAB", "BC", "CB", "BCA", "CBA", "AB", "AC"]

print(permute(list: ["A", "A", "B"]))
// ["AA", "AAB", "ABA", "AB", "BA", "BAA"]

print(permute(list: ["A", "A", "B"], minStringLen: 1))
// ["AAB", "ABA", "B", "BA", "A", "BAA", "AA", "AB"]

print(permute(list: ["A", "A", "B"], minStringLen: 3))
// ["AAB", "ABA", "BAA"]

(JS) Display all the possible character combinations in a specific string, with a predetermined max-length for each output of a character combination

Use a recursive function to iterate through each number of characters that you want enumerated. This simply outputs your results to the console and stores them in an array:

var arr = [];
var index = 0;

function recursive(istr,curstr,count) {
  count--;
  for(var i=0; i<istr.length; i++) {
    var str = curstr + istr.charAt(i);
    if(count>0) {
      recursive(istr,str,count);
    }
    else {
      console.log(str);    // showing answers here
      arr[index++] = str;  // or they are in the array here
    }
  }
}

function enumerate(str, n) {
  for(var i=0;i<n;i++) {
    recursive(str,"",i+1);
  }
} 

enumerate("12345",3);

jsfiddle is here: https://jsfiddle.net/FrancisMacDougall/3p0x4ds5/

get all combinations for a string

This is what I ended up using.

var combinations = function (string)
{
    var result = [];

    var loop = function (start,depth,prefix)
    {
        for(var i=start; i<string.length; i++)
        {
            var next = prefix+string[i];
            if (depth > 0)
                loop(i+1,depth-1,next);
            else
                result.push(next);
        }
    }

    for(var i=0; i<string.length; i++)
    {
        loop(0,i,'');
    }

    return result;
}

Finding all possible permutations of a given string in python

The itertools module has a useful method called permutations(). The documentation says:

itertools.permutations(iterable[, r])

Return successive r length permutations of elements in the iterable.

If r is not specified or is None, then r defaults to the length of the
iterable and all possible full-length permutations are generated.

Permutations are emitted in lexicographic sort order. So, if the input
iterable is sorted, the permutation tuples will be produced in sorted
order.

You'll have to join your permuted letters as strings though.

>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms

['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck',
'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka',
'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc',
'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka',
'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc',
'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas',
'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck',
'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc',
'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actsk',
'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs',
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta',
'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas',
'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta',
'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca',
'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc',
'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs',
'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast',
'kcats']

If you find yourself troubled by duplicates, try fitting your data into a structure with no duplicates like a set:

>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360

Thanks to @pst for pointing out that this is not what we'd traditionally think of as a type cast, but more of a call to the set() constructor.

Generate all possible combinations of strings of certain length in oracle

You don't need PL/SQL to generate an alphabetical sequence. You could do it in pure SQL using Row Generator method.

WITH combinations AS
  (SELECT chr( ascii('A')+level-1 ) c FROM dual CONNECT BY level <= 26
  )
SELECT * FROM combinations
UNION ALL
SELECT c1.c || c2.c FROM combinations c1, combinations c2
UNION ALL
SELECT c1.c
  || c2.c
  || c3.c
FROM combinations c1,
  combinations c2,
  combinations c3
/

The above would give you all possible combinations c1, c2, c3 for single and two characters. For more combinations, you could just add combinations as c4, c5 etc.

Algorithm to find all combinations of a string, maintain order, not fixed length

Here are two ways it could be done without making use of Array#combination. I've also included code for the case when combination is permitted (#3)¹.

1. Map each of the numbers between 1 and 2**n-1 (n being the length of the string) to a unique combination of characters from the string

def string_combinations(str)
  arr = str.chars
  (1..2**str.length-1).map do |n|
    pos = n.bit_length.times.map.with_object([]) { |i,a| a << i if n[i] == 1 }
    arr.values_at(*pos).join
  end.sort
end

string_combinations("wxyz")
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

Discrete probability theory provides us with the equation

sum(i = 1 to n) ( |i| C(n,i) ) == 2^n - 1

where C(n,i) is "the number of combinations of n things taken i at a time".

If the given string is "wxyz", n = "wxyz".length #=> 4, so there are 2**4 - 1 #=> 15 combinations of one or more characters from this string. Now consider any of the numbers between 1 and 16, say 11, which is 0b1011 in binary. Converting this to an array of binary digits, we obtain:

bin_arr = [1,0,1,1]

We now pluck out each character of wxyz for which the corresponding index position in bin_arr equals 1, namely

["w", "y", "z"]

and then join those elements to form a string:

["w", "y", "z"].join #=> "wyz"

Since each number 1 to 15 corresponds to a distinct combination of one or more characters from this string, , we can obtain all such combinations by repeating the above calculation for each the numbers between 1 and 15.

No matter which method you use, the resulting array will contain 2**n - 1 elements, so you are looking at O(2**str.length).

2. Use recursion

def string_combinations(str)
  (combos(str) - [""]).sort
end

def combos(str)
  return [str, ""] if str.length==1
  forward = combos str[1..-1]
  [*forward, *[str[0]].product(forward).map(&:join)]
end

string_combinations("wxyz")
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

Notice that

combos("wxyz")
  #=> ["z", "", "yz", "y", "xz", "x", "xyz", "xy",
  #    "wz", "w", "wyz", "wy", "wxz", "wx", "wxyz", "wxy"] 

includes an empty string, which must be removed, and the array needs sorting. Hence the need to separate out the recursive method combos.

3. Use Array#combination

Here we invoke arr.combination(n) for all values of n between 1 and arr.size and return a (flattened) array comprised of all n return values.

def string_combinations(str)
  a = str.chars
  (1..str.size).flat_map { |n| a.combination(n).map(&:join) }.sort
end

string_combinations "wxyz"
  # => ["w", "wx", "wxy", "wxyz", "wxz", "wy", "wyz", "wz",
  #     "x", "xy", "xyz", "xz", "y", "yz", "z"] 

^{_{1 Since I wrote it before realizing that's not what the OP wanted. ¯\_(ツ)_/¯}}

How to print or display all combination of two string list

List<string> list1 = new List<string>() { "A", "B", "C" };
            List<string> list2 = new List<string>() { "a", "b", "c", "d"};

            list1.ForEach(res =>
            {
                list2.ForEach(res1 =>
                {
                    Console.WriteLine(res + "  " + res1);
                });
            });

And the output is:

---

Related Topics