日期:2014-05-17  浏览次数:20725 次

求助集合划分算法
例如,字符串“25482”,
如果按1组来分需要得到如下结果:
x25482
如果按2组来分得到如下结果:
x2548x2,
x254x82,
x25x482,
x2x5482
如果按3组来分需要得到如下结果:
x254x8x2,
x25x4x82,
x25x48x2,
x2x5x482,
x2x45,x82,
x2x548x2
不能乱序。

------解决方案--------------------
for example
Java code
import java.util.*;
public class Test {
    public static void main(String[] args) throws Throwable {
        String s = "25482";
        for (int i=0; i<s.length(); i++) {
            System.out.printf("-------- %d div test --------\n", i+1);
            for (List<String> l : div(s, i+1)) {
                System.out.println(l);
            }
        }

    }

    public static List<List<String>> div(String src, int count) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (src==null || src.length()==0 || count < 1 || count > src.length()) {
            return result;
        }
        if (count == 1) {
            List<String> list = new ArrayList<String>();
            list.add(src);
            result.add(list);
            return result;
        }

        for (int i=0; i<src.length(); i++) {
            String s = src.substring(0, i+1);
            if (i+1 < src.length()) {
                List<List<String>> t = div(src.substring(i+1), count-1);
                for (List<String> l : t) {
                    l.add(0, s);
                    result.add(l);
                }
            }
        }
        return result;
    }
}

------解决方案--------------------
C# code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "25482";
            int n = 2;

            var data = Enumerable.Range(1, s.Length - 1);
            IEnumerable<int[]> query = data.Select(x => new int[] { x });
            for (int i = 1; i < n; i++)
            {
                query = query.SelectMany(x => data.Select(y => x.Concat(new int[] { y }).ToArray()));
            }
            query = query
                    .Select(x => x.OrderBy(y => y).Distinct().ToArray())
                    .Where(x => x.Count() == n - 1)
                    .OrderByDescending(x => string.Join(",", x))
                    .GroupBy(x => string.Join(",", x))
                    .Select(x => x.First())
                    .Select(x => new int[] { 0 }.Concat(x).ToArray());
            foreach (var item in query)
            {
                Console.WriteLine(string.Join("", s.Select((x, i) => item.Contains(i) ? "x" + x : x.ToString())));
            }
        }
    }
}