当前位置: 代码迷 >> Java Web开发 >> 集合划分算法
  详细解决方案

集合划分算法

热度:4876   发布时间:2013-02-25 21:17:58
求助集合划分算法
例如,字符串“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())));            }        }    }}
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!