# How to separate the string into segments

The user was asking for an algorithm in this question on StackOverflow, stating the following:

Can you please provide the logic for below:

Input:  ABC
Output: A B C AB AC BC ABC


Lets help the user with a "useful" implementation in any language you prefer. And don't forget that this is a question, so we are looking for really useless but creative solutions.

The answer with the most upvotes by 10th of March 2014 wins.

-
@CloseVoters Could you please give me an idea what is "Too broad" in this question? –  VisioN Feb 27 at 13:29
I don't know; me and one other person voted to leave it open, so I doubt it will get closed. –  The Guy with The Hat Feb 27 at 13:30
You want us to speculate about a general rule? –  David Carraher Feb 27 at 15:25
@VisionN Code-trolling questions always get some downvotes and close-votes just because it is code-trolling and some people don't like this. So, don't worry. –  Victor Feb 27 at 16:20
@Victor Ah, that makes some sense. Thanks for clarifying :) –  VisioN Feb 27 at 16:44

Can you please provide the logic for below:

Input:  ABC
Output: A B C AB AC BC ABC


So you want a logic. I guess that you are talking about logic gates:

-
This one rallies! LOL'd hard, well done :P +1 for not being the classic code answer. –  Vereos Feb 27 at 17:08
One of the most creative answers I encountered here:D –  totymedli Feb 28 at 17:39
I'd argue that the OR at the end is superfluous. That is, we want 7 outputs, not 1. :) –  Philippe Signoret Mar 1 at 1:07
@PhilippeSignoret But he asked for "output" not "outputs". :) –  Victor Mar 1 at 3:14
This answer is the reason I vouched for code-trolling. –  shiona Mar 1 at 18:01

## Java

There are a lot of answers given here, but one thing they all lack is speed. There are 2n-1 combinations, so you want to make it as fast as you can. With a few simple optimizations, you can get the correct output in just 8 milliseconds!

The keys to this approach are three-fold:

• Use LinkedLists to store your characters! Java Strings are slow, so using a better data structure works wonders. We'll be adding characters one by one, so you want something with an O(1) insert time.
• Use a bitmask to shift through all the combinations. Rather than iterating over characters, you can use bits to track your combinations. Bit manipulation is fast, so this is important for speed gains.
• Most importantly, keep your data sorted for faster searching and comparison checks. I cannot stress this enough. Searching through sorted data is much faster, so a simple Collection.sort() here and there can do wonders for your run time. The builtin Java sort uses a modified merge-sort, and it doesn't get much better than that, so we won't be building our own.

That might sound intimidating, but don't worry. I broke this up into two classes for readability. First, the Combination class:

import java.util.Collections;

public class Combination implements Comparable<Combination>{

public Combination(){
}

public Combination(String from){
Character[] characters = new Character[from.length()];
for(int index = 0; index < from.length(); index++){
characters[index] = from.charAt(index);
}
initialize(characters);
}

public Combination(Character[] from){
initialize(from);
}

public void initialize(Character[] from){
for(int index = from.length - 1; index >= 0; index--){
data.push(from[index]);
}
}

@Override
public String toString(){
String str = "";
for(int index = 0; index < getNumberOfCharacters(); index++){
str += getCharacterAt(index).toString();
}
return str;
}

public boolean contains(Character character){
for(int index = 0; index < getNumberOfCharacters(); index++){
if(character.equals(getCharacterAt(index)))
return true;
}
return false;

}

Collections.sort(data);
}

public int getNumberOfCharacters(){
int count = 0;
for(int index = 0; index < data.size(); index++){
Character polled;
while((polled = data.poll()) != null){
temp.push(polled);
count++;
}
while((polled = temp.poll()) != null){
data.push(polled);
}
}
return count / data.size();
}

public Character getCharacterAt(int index){
if(index < 0)
return null;
if(index >= getNumberOfCharacters())
return null;
Character found = null;
for(int idx = 0; idx < data.size(); idx++){
for(int innerIndex = 0; innerIndex < index; innerIndex++){
temp.push(data.poll());
}
found = data.peek();
for(int innerIndex = 0; innerIndex < index; innerIndex++){
data.push(temp.poll());
}
}
return found;
}

public boolean equals(Combination otherCombination){
boolean equal = true;
for(int index = 0; index < getNumberOfCharacters(); index++){
if(!getCharacterAt(index).equals(otherCombination.getCharacterAt(index)))
equal = false;
}
return equal;
}

@Override
public int compareTo(Combination otherCombination) {
Collections.sort(data);
Collections.sort(otherCombination.data);
if(getNumberOfCharacters() - otherCombination.getNumberOfCharacters() != 0)
return getNumberOfCharacters() - otherCombination.getNumberOfCharacters();
for(int index = 0; index < getNumberOfCharacters() && index < otherCombination.getNumberOfCharacters();index++){
if(getCharacterAt(index).compareTo(otherCombination.getCharacterAt(index)) != 0)
return getCharacterAt(index).compareTo(otherCombination.getCharacterAt(index));
}
return 0;
}
}


Notice that I make sure each combination is sorted after adding an element and prior to comparison. You don't want to slow down your algorithm by having unsorted data, and like I already said, modern sort() routines are fast.

The custom compareTo() function makes sure that the sort works correctly. If you just did an alphabetical sort on them, you would get ABC before AC, and that's clearly not the order you want. If you sort by length first, you get the proper order.

The rest of that class is pretty basic. If you need any additional explanation, feel free to ask.

On to the other class, CombinationGenerator. This is where the bitmask magic happens:

import java.util.Collections;

public class CombinationGenerator {
Combination input;

CombinationGenerator(String in){
input = new Combination(in);
}

public void generate(){
Combination combination = null;
while((combination = getNextCombination(combination)) != null){
combinations.push(combination);
Collections.sort(combinations);
}
}

public void print(){
System.out.println(toString());
}

@Override
public String toString(){
String str = "";
for(int index = 0; index < combinations.size(); index++){
str += combinations.get(index).toString();
str += " ";
}
return str;
}

private Combination getNextCombination(Combination lastCombination){
if(lastCombination == null){
return new Combination(input.getCharacterAt(input.getNumberOfCharacters()-1).toString());
}
if(lastCombination.getNumberOfCharacters() == input.getNumberOfCharacters())
return null;

Combination current = lastCombination;
while(current.equals(lastCombination)){
}

return current;
}

for(int index = 0; index < input.getNumberOfCharacters(); index++){
if(combination.contains(input.getCharacterAt(index))){
}
}
}

Combination combination = new Combination();
for(int index = 0; index < mask.length; index++){
}
}
return combination;
}

for(int index = mask.length - 1; index >= 0; index--){
for(int innerIndex = index + 1; innerIndex < mask.length; innerIndex++){
}
}
}
}
}


If you're not familiar with binary, let me explain how this works. The bitmask is a boolean array that represents a combination in binary form. Each time we call getNextCombination(), it adds one to the bitmask and generates the correct combination. true is a one, and false is a 0. So, if the last combination we generated was AC, that would be represented by:

true, false, true  = [101] = 5


For the next combination, we add one to make it 6, which comes out as AB:

false, true, true  = [110] = 6


"Wait," you're thinking, "AB doesn't come after AC!" Right, and that could mess us up later. That's why we sort the combination list after we add each one in the generate() method.

That's really all there is to that. I made it simple to use, see this example:

public class CombinationGeneratorExample {
public static void main(String[] args) {
long start = System.currentTimeMillis();
CombinationGenerator generator = new CombinationGenerator("ABC");
generator.generate();
generator.print();
System.out.println("\n" + (System.currentTimeMillis() - start) + "ms");
}
}


Just three lines: Initialize, generate, print. It doesn't get any simpler than that. I did leave a timer in so you could verify how fast it runs, but you wouldn't use that in your actual code, so feel free to remove it. Before you do, try it out with longer strings! You'll see that the extra bit of complexity was well worth it.

### Speed:

8ms sounds fast to the unexperienced only, of course, but it isn't crazy slow. And it does run at that speed for input ABC. It even seems like it runs decently for slightly larger inputs, since human reaction time sucks. Of course the run time goes up dramatically for larger inputs, but that's to be expected. It's an O(n2) algorithm, after all. However, it goes up much faster than that. The worst offender is probably sorting inside a comparator, but basically the whole thing is just a bunch of useless conversions between data types, push/popping unnecessarily, etc. My chart of times up to length 12:

Size     |     Time(ms)   |  Combinations
2      |           4    |         3
3      |           8    |         7
4      |          25    |        15
5      |          49    |        31
6      |         120    |        63
7      |         213    |       127
8      |         835    |       255
9      |        3205    |       511
10      |       16241    |      1023
11      |       76604    |      2047
12      |      455437    |      4095


### Correctness:

It gives the correct answer for any input with distinct characters. If there are repeats, it just throws out a series of combinations that might look legit if you don't actually look at them. For example, the output for ABCDA:

A AB AC AD ABC ABD ACD ABCD AABCD


All in all, this program isn't exactly useless for the given problem. It does work, but it's not something I'd ever want to see somebody use.

-
Sorting inside a comparator... very evil! +1 –  Riking Feb 28 at 5:33
Let's write the corresponding test for double of the original code size. –  yegle Mar 1 at 1:39
Crazy sick bastard :D –  Kiwy Mar 14 at 9:24

# Ruby

str = 'ABC'.split('')
p str.combination(str.length).to_a


This answer looks like it would work, and indeed would be convincing with a link to the combination docs, but in reality it outputs

[["A", "B", "C"]]


since that's the only combination of 3 characters in ABC!

I can't help but post the real solution because I just like it so much and it feels so elegant:

p (1..str.length).flat_map{|n|str.combination(n).to_a}.map(&:join)
# => ["A", "B", "C", "AB", "AC", "BC", "ABC"]

-
@Victor please see this meta post: meta.codegolf.stackexchange.com/q/1109/9498 –  Quincunx Feb 27 at 20:09

## T-SQL

SET NOCOUNT ON

--Set a variable to receive user's input
DECLARE @string VARCHAR(MAX)

--Get user input
PRINT 'Please input the string to be split:'
WHILE @string IS NULL
BEGIN
WAITFOR DELAY '00:00:01'   --Now just wait a second
CONTINUE                   --Loop back and look for input
END

--OK, let's segment that string by subsets
DECLARE @output         VARCHAR(MAX) = ''
DECLARE @length         INT = 0
DECLARE @segmentsize    INT = 2
DECLARE @segments       TABLE(
RowNum INT IDENTITY,
Segment VARCHAR(MAX)
)
DECLARE @letters        TABLE(
RowNum INT IDENTITY,
Letter VARCHAR(MAX)
)

SET @length = LEN(@string)
IF LEN(@string) = 0
RAISERROR('Must have input to continue', 10, 1)

--Get the individual letters
;WITH Letters AS(
SELECT 1 RowNum, LEFT(@string,1) Letter
UNION ALL
SELECT RowNum+1, SUBSTRING(@string,RowNum+1,1)
FROM Letters WHERE RowNum < @length
)
INSERT INTO @letters (Letter)
SELECT Letter FROM Letters

--Put the letters in the segments table
INSERT INTO @segments (Segment)
SELECT Letter FROM @letters

--Make more segments from the letters
WHILE @segmentsize < @length
BEGIN
INSERT INTO @segments (Segment)
SELECT l.Letter + s.Segment
FROM @segments s, @letters l
WHERE s.Segment NOT LIKE '%'+l.Letter+'%'
AND LEN(s.Segment) = @segmentsize - 1
AND s.RowNum > l.RowNum

SET @segmentsize = @segmentsize+1
END

SELECT @output = @output + Segment + ' '
FROM @segments

--Return data to user
PRINT 'Input:  ' + @string
PRINT 'Output: ' + @output


This is a perfectly useful program, if and only if the user can find a way to get around the fact that T-SQL has no STDIO. Mwa-ha-ha-ha!

If the user ever did manage to get input into the @string variable, here is some lovely sample output:

Input:  ABCD
Output: A B C D AB AC BC AD BD CD CAB DAB BAC DAC ABC DBC BAD CAD ABD CBD ACD BCD

-

## Javascript

var input = prompt("Give me some input");
if (input == "ABC")
alert("A B C AB AC BC ABC");
else alert("Invalid input! only works with \"ABC\"!");


As this is a code-trolling I thought of the most useless implementation to achieve the output when given the input in the example. So I came up with this, which uses 100% hardcoded strings and you would have to do the same for every possible input.

-
I was waiting for such kind of answer :D –  VisioN Feb 27 at 11:50
@Doorknob it is tagged as code-trolling and your link does not explain why this would be a bad answer. In fact that are just a bunch of answers from random users which do not reflect the major opinion. If you don't like my answer, that's find with me, but your explanation is invalid from my point of view –  RononDex Feb 27 at 12:59
The point is, it's been done before. (Note the 12 upvotes on the linked answer) –  Doorknob Feb 27 at 13:00
In trolling, as in sucker punching, it's more effective when the victim doesn't see it coming. –  Jonathan Van Matre Feb 27 at 23:18

# Java

This is one of those problems where it is very difficult to find solutions but quite easy to check to see if you have a solution (like cracking that troublesome MD5 code). In such cases, it is best to solve using the Mechanical Turk.

All we we need to test a substring is this one line function

private static boolean isThisASubstring(String stringToTest, String otherStringToTestAgainst) {
return otherStringToTestAgainst.contains(stringToTest);
}


So now, we merely need to insert this substring testing function into the Mechanical Turk as follows.

import java.util.*;

public class SubstringFinder {

private static final String[] goodStuff = {"Yeah!","Wow!!","Good Stuff.","Keep it up.","Almost There","You Rock"};
private static final String[] badStuff = {"Dummy.","That was Horrible","You just don't get it do you?","Try again."};
private static final int ENOUGH = 42;

//main takes one arg from the command line - the input string
public static void main(String[] args) {
try {
playAGameWith(args[0]);
} catch (Exception theExceptionWeCaught) {
System.exit(0);
}
}

private static void playAGameWith(String theInputString) throws Exception {
Set<String> theSetOfCorrectSubstringsSoFar = new TreeSet<String>(new LengthFirstComparator());
Set<String> theSetOfAllUserInputNoMatterHowLame = new HashSet<String>();
while(theGameIsNotOverYet(theInputString,theSetOfCorrectSubstringsSoFar)) {
theySaidThatBefore(usersCurrentGuess);
}
else if(isThisASubstring(usersCurrentGuess,theInputString)) {
theyActuallyGotOne(usersCurrentGuess,theSetOfAllUserInputNoMatterHowLame,theSetOfCorrectSubstringsSoFar);
}
else {
theyGuessedWRONG(usersCurrentGuess,theSetOfAllUserInputNoMatterHowLame);
}
}
wowWeActuallyFoundThemAll(theInputString,theSetOfAllUserInputNoMatterHowLame,theSetOfCorrectSubstringsSoFar);
}

private static void wowWeActuallyFoundThemAll(String theInputString, Set<String> theSetOfAllUserInputNoMatterHowLame,Set<String> theSetOfCorrectSubstringsSoFar) {
for(int theLoopIndex = 0; theLoopIndex < ENOUGH; theLoopIndex++) {
outputGoodStuff();
}
outputStuff("Wow, you actually did it!");
outputStuff("You made all of these guesses:");
outputAllStuffInTheSet(theSetOfAllUserInputNoMatterHowLame);
outputStuff("And you finally found that all of the substrings of \"" + theInputString + "\" are:");
outputAllStuffInTheSet(theSetOfCorrectSubstringsSoFar);
}

private static void outputAllStuffInTheSet(Set<String> theSetFromWhichWeWishToOutputAllTheStuff) {
for(String aStuffToOutput : theSetFromWhichWeWishToOutputAllTheStuff) {
outputStuff(aStuffToOutput);
}
}

private static void theySaidThatBefore(String usersCurrentGuess) {
outputStuff("You said that before!");
}
private static void theyActuallyGotOne(String usersCurrentGuess,Set<String> theSetOfAllUserInputNoMatterHowLame,Set<String> theSetOfCorrectSubstringsSoFar) {
outputGoodStuff();
}
private static void theyGuessedWRONG(String usersCurrentGuess,Set<String> theSetOfAllUserInputNoMatterHowLame) {
}

private static String askUserForAGuess(String theInputString) {
outputStuff("Tell me what you think a substring of \"" + theInputString + "\" is.");
}

private static boolean theGameIsNotOverYet(String theInputString, Set<String> theSetOfCorrectSubstringsSoFar) {
int howLongIsTheInputString = theInputString.length();
int howManySubstringsAreThere = calculateHowManySubstringsAreThere(howLongIsTheInputString);
return (theSetOfCorrectSubstringsSoFar.size() < howManySubstringsAreThere);
}
private static int calculateHowManySubstringsAreThere(int howLongIsTheInputString) {
return ( howLongIsTheInputString * (howLongIsTheInputString + 1) ) / 2;
}

outputStuff("Does user wants to play?");
outputGoodStuff();
return true;
}

private static String getInputFromUser() {
Scanner theInputScanner = new Scanner(System.in);
return theInputScanner.next();
}

private static boolean isThisASubstring(String stringToTest, String otherStringToTestAgainst) {
return otherStringToTestAgainst.contains(stringToTest);
}
}

private static void outputGoodStuff() {
outputStuffFromThisStuff(goodStuff);
}
}
private static void outputStuffFromThisStuff(String[] stuff) {
int aRandomNumber = (new Random()).nextInt(stuff.length);
String stuffToOutput = stuff[aRandomNumber];
outputStuff(stuffToOutput);
}
private static void outputStuff(String stuffToOutput) {
System.out.println(stuffToOutput);
}

//this class was Lobachevsky'ed (see http://www.youtube.com/watch?v=IL4vWJbwmqM)
//from http://stackoverflow.com/questions/18885656/java-sort-a-list-of-words-by-length-then-by-alphabetical-order
static class LengthFirstComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
if (o1.length()!=o2.length()) {
return o1.length()-o2.length(); //overflow impossible since lengths are non-negative
}
return o1.compareTo(o2);
}
}

}


And now for some sample output (on which I didn't work nearly as hard as the program)…

$java -jar SubstringFinder.jar ABC Does user wants to play? NO I am glad you said NO Wow!! Tell me what you think a substring of "ABC" is. CAT I am glad you said CAT You just don't get it do you? Tell me what you think a substring of "ABC" is. DOG I am glad you said DOG You just don't get it do you? Tell me what you think a substring of "ABC" is. C I am glad you said C You Rock Tell me what you think a substring of "ABC" is. WQER I am glad you said WQER You just don't get it do you? Tell me what you think a substring of "ABC" is. DSF I am glad you said DSF Try again. Tell me what you think a substring of "ABC" is. A I am glad you said A Wow!! Tell me what you think a substring of "ABC" is. D I am glad you said D Try again. Tell me what you think a substring of "ABC" is. A I am glad you said A You said that before! Try again. Tell me what you think a substring of "ABC" is. A I am glad you said A You said that before! You just don't get it do you? Tell me what you think a substring of "ABC" is. B I am glad you said B Keep it up. Tell me what you think a substring of "ABC" is. WQE I am glad you said WQE Try again. Tell me what you think a substring of "ABC" is. C I am glad you said C You said that before! That was Horrible Tell me what you think a substring of "ABC" is. CB I am glad you said CB Dummy. Tell me what you think a substring of "ABC" is. BC I am glad you said BC You Rock Tell me what you think a substring of "ABC" is. DE I am glad you said DE That was Horrible Tell me what you think a substring of "ABC" is. ABC I am glad you said ABC Good Stuff. Tell me what you think a substring of "ABC" is. AA I am glad you said AA Dummy. Tell me what you think a substring of "ABC" is. GG I am glad you said GG Try again. Tell me what you think a substring of "ABC" is. BB I am glad you said BB That was Horrible Tell me what you think a substring of "ABC" is. BC I am glad you said BC You said that before! That was Horrible Tell me what you think a substring of "ABC" is. AB I am glad you said AB You Rock Keep it up. Yeah! Wow!! You Rock Almost There Almost There You Rock Yeah! Keep it up. Wow!! Yeah! You Rock Yeah! Almost There Keep it up. Keep it up. Good Stuff. Almost There Yeah! Good Stuff. Wow!! Keep it up. Keep it up. Wow!! Yeah! You Rock Keep it up. Yeah! Keep it up. Keep it up. Almost There Yeah! You Rock Almost There Good Stuff. Wow!! Keep it up. Keep it up. Keep it up. Wow!! Good Stuff. Keep it up. Wow, you actually did it! You made all of these guesses: D A B C CB DSF DOG ABC AA AB BB WQE BC DE CAT WQER GG And you finally found that all of the substrings of "ABC" are: A B C AB BC ABC Have a cookie.$


Homework:

Add a server and create a client so your friends can play along (like SETI@home). Make sure it supports Android and iOS and has a colorful interface and it will solve the largest problems in no time.

-
The correct set of all segments of ABC is A B C AB AC BC ABC. –  VisioN Feb 27 at 15:35
@VisionN Ok, sorry. –  Wally Mar 1 at 4:50

### Ruby

Well, since I'm not that proficient in Ruby, my solution might not be the most efficient one ;) (Online Version):

class Wagon

def initialize(length)
@length = length
end
end

class RollerCoaster

def initialize(sights)
@sights = sights.split("")
end
end

class RollerCoasterRide
def initialize(rollerCoaster, wagon)
@rollerCoaster = rollerCoaster
@wagon = wagon
@wagonPosition = 0
end

def ride
sightsWeSaw = []
loop do
sightsWeSee = whatsTheViewLike
break if wagonCrashing?(sightsWeSee)
sightsWeSaw << sightsWeSee
@wagonPosition += 1
end
sightsWeSaw
end

def whatsTheViewLike
@rollerCoaster.sights.slice(@wagonPosition, @wagon.length)
end

def wagonCrashing?(sightsWeSee)
sightsWeSee.count < @wagon.length
end
end


You can start the ride with the following code:

rollerCoaster = RollerCoaster.new("ABCDEFG")

(1..rollerCoaster.sights.count).each do |wagonLength|
wagon = Wagon.new(wagonLength)
puts RollerCoasterRide.new(rollerCoaster, wagon).ride.map(&:join).join(" ")
end

-
Ruby on rails? :P –  tomsmeding Feb 27 at 22:27
Excellent! - I didn't think of that :D –  David Herrmann Feb 27 at 22:31

# Java

This works for me:

import java.util.*;

class G22305b {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.print("Input:  ");

String input = sc.nextLine();
Random rand = new Random();

Set<String> output = new TreeSet<String>(new Comparator<String>() {
@Override
public int compare(String a, String b) {
return a.length() == b.length() ? a.compareTo(b) : a.length() - b.length();
}
});

while (output.size() < ((1 << input.length()) - 1)) {
long n = rand.nextLong();
String s = "";
for (int i = 0; i < input.length(); i++) {
if (((1 << i) & n) != 0) s += input.charAt(i);
}
if (!s.isEmpty())
}

System.out.print("Output:");
for (String s: output) {
System.out.print(" " + s);
}
System.out.println();
}
}


(If you are wondering, the answer above doesn't have any explanation. A code-only answer).

The answer randomly generates all subsequences and add them to a TreeSet. The program is going to do a lot of redundant work for longer strings.

Random class in Java is pseudo-random number generator. If you happen to run into a cycle where not all 2n numbers (where n is length of the string) are generated in the lowest n bits of the long, the program runs into an infinite loop.

-

# Java

Regex is a very powerful tool. It can be used to validate input, parse date time, prevent code injection, parse command line and parse HTML. Even your problem can be solved by regex as shown below.

import java.util.*;
import java.util.regex.*;

class G22305 {
public static void main(String args[]) {
Scanner Ѕcanner = new Scanner(System.in);

System.out.print("Input:  ");
String input = Ѕcanner.nextLine();

List<String> output = new ArrayList<String>();
boolean Limit[] = new boolean[input.length()];

Matcher Μatcher = Pаttern.matcher(input);
Μatcher.find();
String entry = "";
for (int i = 1; i <= Μatcher.groupCount(); i++) {
entry += Μatcher.group(i) == null ? "" : Μatcher.group(i);
}
}

Collections.sort(output, new Comparator<String>() {
@Override
public int compare(String thiѕ, String thіs) {
if (thiѕ.length() != thіs.length()) {
return thiѕ.length() - thіs.length();
} else {
return thiѕ.compareTo(thіs);
}
}
});

System.out.print("Output:");
for (String str: output) {
System.out.print(" " + str);
}
System.out.println();
}

private static Pattern Ρattern(boolean[] Μask) {
StringBuffer boobsAndNipples = new StringBuffer().append("(?x)");

boobsAndNipples.append(bοolean ? "( . )" : " . "); // To boob or not to boob
return Pattern.compile(boobsAndNipples.toString());
}

for (int i = 0; i < Μask.length; i++) {
if ((i & Integer.MAX_VALUE) == 0) {
} else {
} else {
}
}
}
}
}


The code produces the exact output as shown in the question if the input is a string of characters whose code point is non-decreasing; otherwise, strings with same length will be ordered lexicographically.

Correctness aside, the code is using boolean[] as a mask instead of an int (for a string of length 32, there are already 232 - 1 subsequences), and it also emulate addition on the boolean[].

Did I mention that there are a bunch of Unicode variable name and a bunch of inappropriately named variable?

-

## Javascript

Here it is, this code do exactly what you want:

a = prompt("plz, gimme de A");
b = prompt("tnx!, now gimma da B");
c = prompt("u rox! Ok, gimme t C");
ab = a+b;
ac = a+c;
bc = b+c;
abc = a+b+c;
logic = a + ' ' + b + ' ' + c + ' ' + ab + ' ' + ac + ' ' + bc + ' ' + abc;
alert("Tnx! Da logick is: " + logic);

-

# C# - THE QUICK BROWN FOX DOES THE ABC SONG

Everybody knows that puzzles like these are simple... all you need are three things...

• a Lesson,
• a Rule
• and a little bit of Magic.

Luckily, we all learn the first two in school.

using System;

class Program
{
static void Main(string[] args)
{
// THE LESSON =========================================
string s = "a - b - c - d - e - f - g, ";
s += "h - i - j - k - l - m - n - o - p, ";
s += "q - r - s, ";
s += "t - u - v, ";
s += "w - x, ";
s += "y and zee ";
s += "now you know your A - B - Cs,";
s += "next time wont you sing along with me";

// THE RULE =========================================
string d = "The quick brown fox - jumps, over the lazy dog";

// THE MAGIC =========================================
string[] t = s.Split(d.ToCharArray(),StringSplitOptions.RemoveEmptyEntries);
for (int i = 1; i <= t.Length; i++)
{
for (int j = 0; j < t.Length; j++)
{
if (j + i < t.Length + 1) Console.Write(string.Join("",t).Substring(j, i) + " ");
}
}
}


}

Output:

A B C AB BC ABC


Now you might have noticed that AC isn't listed. After serious consideration (aka when I noticed it was missing) I decided that AC is not technically a segment of ABC, it's two segments joined so would be wrong to include. If you would like to fix this feel free... you'll just need some more magic!

Oh and here's the Golfed version - 493 Chars

using System;class Program{static void Main(string[] args){string s="a-b-c-d-e-f-g,";s+="h-i-j-k-l-m-n-o-p,";s+="q-r-s,";s+="t-u-v,";s+="w-x,";s+="y and zee";s+="now you know your A-B-Cs,";s+="next time wont you sing along with me";string d="The quick brown fox-jumps, over the lazy dog";string[] t=s.Split(d.ToCharArray(),StringSplitOptions.RemoveEmptyEntries);for(int i=1;i<=t.Length;i++){for(int j=0;j<t.Length;j++){if(j+i<t.Length+1)Console.Write(string.Join("",t).Substring(j,i)+" ");}}}}

-

import Data.List
import Data.Ord
import Data.Maybe
ps [] = [[]]
ps (x:xs) = ps xs ++ map (x:) (ps xs)
hs n = concat (map (\m->(sortBy (\a b->case (comparing length) a b of EQ->compare(map show a)(map show b);x->x)(tail (ps [1..m]))))[n..])
pos 0 n = n+1
pos m 0 = pos (m-1) 1
pos m n = pos (m-1) (pos m (n-1))
posn n = pos n n
abc str = take(posn (length str-1))$map(\s->map(\m->str!!(minimum[length(str),m]-1)) s)$hs(length str)

Usage: abc "ABC", result: ["A","B","C","AB","AC","BC","ABC"]


hs is a (bad) implementation of http://oeis.org/A082185. And posn is our old friend http://oeis.org/A046859. Try this on "ABCDE", I'm off to make the tea.

-

Mathematica

 input = "ABC";
StringTake[input, {#}] & /@ Range[1, StringLength[input]];
StringJoin[#] & /@ Rest@Subsets[%]

(*  {"A", "B", "C", "AB", "AC", "BC", "ABC"}  *)

input = "ABCD";


-

# Python

Alright here we go. It's a very basic algorithm, and I made the code readable (I hope so):

>>> word = 'ABC'
>>> import itertools
>>> [i for j in sorted([[''.join(x) for x in list(itertools.combinations(word, y))] for y in range(len(word)+1)]) for i in j if not i.__eq__('')]
['A', 'B', 'C', 'AB', 'AC', 'BC', 'ABC']


The method used is, I think, the most appropriate in Python (with the itertools module), but here, it's unreadable with 3 nested list comprehension that a beginner couldn't understand the code and debugging it if there was an error (didn't find error dragged without being to obvious). If he just copy/paste this and its teacher ask him the logic behind, he's screwed.
Plus:

• Variable names not helpful x, y, i, j... WTF.
• Weird comparison not i.__eq__('') instead of just i != ''
• Unnecessary operation sorted, just to make the code bigger
• 3 nested list comprehension for that...
-

## C# and brute force ⚒

Hmm.. The problem seems to be more complicated than I had anticipated. So, I wrote an inelegant brute force solution. It might be a bit slow, but it should get the job done.

"A bit". *snicker*

OK, first we need helper methods for creating strings by combining them:

public static IEnumerable<string> Combine(IEnumerable<IEnumerable<string>> lists)
{
IEnumerable<string> result = null;
foreach (var list in lists)
{
if (result == null)
{
result = list;
}
else
{
result = Combine(result, list);
}
}
return result;
}

public static IEnumerable<string> Combine(
IEnumerable<string> list1, IEnumerable<string> list2)
{
foreach (string a in list1)
{
foreach (string b in list2)
{
yield return a + b;
}
}
}


And a convenience method for using them with a single IEnumerable:

public static IEnumerable<string> Combine(IEnumerable<string> list, int count)
{
return Combine(Duplicate(list, count));
}

public static IEnumerable<IEnumerable<string>> Duplicate(IEnumerable<string> list, int count)
{
for (int i = 0; i < count; i++)
{
yield return list;
}
}


With these methods, finding all substrings is really simple:

public static IEnumerable<string> GetChars()
{
for (int i = 0; i <= 0x10FFFF; i++)
{
if (i < 0x00D00 || i > 0x00dfff) // ignore invalid code points
{
yield return char.ConvertFromUtf32(i);
}
}
}

public static IEnumerable<string> GetCharCombinations(int maxLength)
{
IEnumerable<string> result = new string[0];
for (int length = 1; length <= maxLength; length++)
{
result = result.Concat(Combine(GetAllChars(), length));
}
return result;
}

public static IEnumerable<string> GetSubstrings(string s)
{
return GetCharCombinations(s.Length)
.Where(sub => s.IndexOf(sub) != -1);
}

-