[Yorie]

 
public class main
{
	public static void main(String[] args)
	{
		String sample = "Строка {1:2:3}, атататата {4:5:6}, ололо {7:8:9}";
		for (String str : replacer(sample))
		{
			System.out.println(str);
		}
	}
 
	private static ArrayList<String> replacer(String str)
	{
		ArrayList<String> results = new ArrayList<String>();
		Pattern pattern = Pattern.compile("(\\{(.*?)\\})");
		Matcher matcher = pattern.matcher(str);
 
		if (matcher.find())
		{
			String[] nums = matcher.group(2).split(":");
			for (String num : nums)
			{
				String result = str.replace(matcher.group(1), num);
				results.addAll(replacer(result));
			}
		}
		else
		{
			results.add(str);
		}
		return results;
	}
}
 
Code: Java

Имхо Учим мат. часть по рекурсивным функциям.