How to get N random string from a {a1|a2|a3} format string?

Question

Take this string as input:

string s1="planets {Sun|Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune}{?|!|.}"
string s2="some text {morning,night,evening} some text{?|!|.}"

How would I choose randomly N from the set, then join them with comma. The set is defined between {} and options are separated with | pipe The order is maintained. String can have multiple sets {}.

Some output could be:

string output1="planets Sun, Venus.";
string output2="planets Neptune!";
string output3="planets Earth, Saturn, Uranus, Neptune.";
string output4="planets Uranus, Saturn.";// bad example, order is not correct
string output5="some text morning!";

Java 1.5

Answer 1

Stick the planets into an array, and remove random elements until you have enough. There are cuter solutions, algorithmically speaking, but for the amount of data you're dealing with, this is quick and simple.

Answer 2

I am not sure about the syntax of java - but it should be something like this.

string[] split = s.split("|");
Random r = new Random();
int first = r.nextInt(split.length);
string planets = "planets " + split[first++];
for (; first < split.length; first++)
{
    if (r.nextInt(2) == 1)
         planets += " " + split[first];
}

Answer 3

I tested this Java program and it works:

import java.util.Random;

/** @author Daniel Trebbien */
// License: Public Domain
public class SO2965185 {
    public static String randomFormat(final String templ) {
        int i = templ.indexOf('{');
        if (i < 0) {
            return templ;
        }
        else {
            Random r = new Random();

            int prevI = 0;
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(templ, prevI, i);
                int j = templ.indexOf('}', i + 1);
                if (j < 0)
                    throw new java.util.MissingFormatArgumentException(templ.substring(i));
                int pipeCount = 0;
                for (int k = templ.indexOf('|', i + 1); i < k && k < j; k = templ.indexOf('|', k + 1))
                    ++pipeCount;
                if (pipeCount == 0) {
                    sb.append(templ, i + 1, j);
                }
                else {
                    String m0Selection;
                    final int m0 = r.nextInt(pipeCount + 1); // must pick one from each set
                    if (m0 >= pipeCount) {
                        m0Selection = templ.substring(templ.lastIndexOf('|', j - 1) + 1, j);
                    }
                    else {
                        int k = i + 1;
                        int m = m0;
                        for(; m > 0; --m)
                            k = templ.indexOf('|', k) + 1;
                        m0Selection = templ.substring(k, templ.indexOf('|', k + 1));
                    }

                    int selectionCount = 0;
                    for (int n = 0; n <= pipeCount; ++n) {
                        if (n == m0) {
                            if (selectionCount != 0)
                                sb.append(", ");
                            sb.append(m0Selection);
                            ++selectionCount;
                        }
                        else if (r.nextBoolean()) {
                            int m = n;
                            if (selectionCount != 0)
                                sb.append(", ");
                            if (m >= pipeCount) {
                                sb.append(templ, templ.lastIndexOf('|', j - 1) + 1, j);
                            }
                            else {
                                int k = i + 1;
                                for(; m > 0; --m)
                                    k = templ.indexOf('|', k) + 1;
                                sb.append(templ, k, templ.indexOf('|', k + 1));
                            }
                            ++selectionCount;
                        }
                    }
                }
                prevI = j + 1;
                i = templ.indexOf('{', j + 1);
            } while(i >= 0);
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        System.out.println(randomFormat("test"));
        System.out.println(randomFormat("{oneOption}"));
        System.out.println(randomFormat("{first|second}"));
        String s1 = "planets {Sun|Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune}{?|!|.}";
        System.out.println(randomFormat(s1));
        //System.out.println(randomFormat("jjj{test"));
    }
}

This program prints something like:

test
oneOption
first, second
planets Sun, Mercury, Jupiter, Neptune?, !, .

and

test
oneOption
second
planets Sun, Jupiter, Saturn!, .

and

test
oneOption
first
planets Venus, Earth, Jupiter, Saturn, Uranus, Neptune.

You'll have to forgive the mess a little because I originally wrote code for a slightly different problem :)

The code picks random combinations of entries having at least one entry from each set. So, for a set with N entries, there are 2^N - 1 combinations that can be generated. Also, keep in mind the probability that there are exactly M entries in the random combination:

P(exactly M entries in generated combination) = (N choose M) divided by (2^N - 1)

Example: N = 9 ("{Sun|Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune}").

P(exactly 2 entries in generated combination) = 0.0704

Answer 4

Here is another option. This one only chooses 1 element from {|||} sets, and chooses between 1 and N elements in {,,,} sets, separating them with commas. Nice programming challenge.

public static String generateVariant(String s) {
    Pattern p = Pattern.compile("[{]([^}]+)[}]");
    Matcher m = p.matcher(s);
    StringBuilder output = new StringBuilder();

    int offset = 0;
    while (m.find()) {
        output.append(s.substring(offset, m.start()));
        String[] choices = m.group(1).split("[|,]");

        // if '|' used as separator, only echo 1 random choice
        int n = m.group(1).contains("|") ? 1
                : (int) (Math.random() * (choices.length - 1)) + 1;

        // permutation with n random elements
        int[] permutation = new int[choices.length];
        for (int i = 0; i < choices.length; i++) {
            permutation[i] = i;
        }
        for (int i=0; i<n; i++) {
            int r = (int)(Math.random() * (choices.length - i)) + i;
            int aux = permutation[r];
            permutation[r] = permutation[i];
            permutation[i] = aux;
        }

        // sort and echo first n
        Arrays.sort(permutation, 0, n);
        for (int i=0; i<n; i++) {
            output.append((i == 0 ? "" : ", ") + choices[permutation[i]]);
        }
        offset = m.end();
    }
    output.append(s.substring(offset, s.length()));
    return output.toString();
}

public static void main(String[] args) {
    String s1 = "planets {Sun,Mercury,Venus,Earth,Mars,Jupiter,Saturn,Uranus,Neptune}{?|!|.}";
    for (int i = 0; i < 10; i++) {
        System.err.println(generateVariant(s1));
    }
}

Yes, generating a permutation is overkill for the {|||} sets. Here is a shorter and simpler version, where the distribution of the number of choices is no longer uniform (inspired by Daniel Trebbien's answer):

public static String generateVariant(String s) {
    Pattern p = Pattern.compile("[{]([^}]+)[}]");
    Matcher m = p.matcher(s);
    StringBuilder output = new StringBuilder();
    Random r = new Random();

    int offset = 0;
    while (m.find()) {
        output.append(s.substring(offset, m.start()));
        String[] choices = m.group(1).split("[|,]");
        // if '|' used as separator, only echo 1 random choice
        if (m.group(1).contains("|")) {
            output.append(choices[r.nextInt(choices.length)]);
        } else {
            boolean first = true;
            for (int i=0; i<choices.length; i++) {
                if (r.nextBoolean()) {
                    output.append((first ? "" : ", ") + choices[i]);
                    first = false;
                }
            }                
        }
        offset = m.end();
    }
    output.append(s.substring(offset, s.length()));
    return output.toString();
}