技术宅社区 | Z站有爱，有技术，有你 ^_^)y»论坛 › 历史 › 废弃IT区 › 研究院 › 【趣味编程】排列组合的应用

查看: 1767|回复: 11

[交流] 【趣味编程】排列组合的应用

该用户从未签到

10 主题	5 好友	1441 积分

Continue

积分: 1441

发表于 2012-4-12 19:20:54 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

本帖最后由 LonghronShen 于 2012-4-12 23:57 编辑

问题描述：

在彩票分析中最重要的一环就是对数据的频度分析。而数据样本就是历次彩票的开奖号码。有人认为可以通过统计学分析来统计出频度规律，并以此指导彩票购买。

已知：一定数量的彩票摇奖结果，格式类似于：

2007048 0211 12 15 17 28

我们可以根据空格来把这一条记录分为几个字段：开奖期号，号码1，号码2……号码6。事实上，这是一个典型的33选6的玩法得到的数据。每个号码的取值范围是1-33，在摇奖过程中将得到的是无重复的6个数字。其实，每一次的开奖结果就是一个

组合中的一种。当然，这里33和6作为组合数的参数，在不同的彩票玩法中不同。虽然还有一些其它类型的彩票，但是我们目前仅仅局限于这种

的数字组合类型的彩票。

彩票分析中最常见的是比较算法。常规比较对象有两种。

玩法1：

遍历数据库中的每条记录，并且和除它自身以外的所有项进行比较，统计出每条记录和当前记录有0个相同、1个相同、2个相同……n个相同的数目。根据相似度来选择较好的号码进行投注。

玩法2：

生成

的全组合（

），然后遍历所有可能，和数据库中所有条目进行比较。统计该子组合被包含的情况：0个相同、1个相同、2个相同……k个相同。在彩票界，如果某种组合被包含在某次的开奖结果中，则称这组合和这次的开奖结果“相生”，反之被称为“相克”。

要求：

请根据所学的C++知识（不局限于书本），实现一个

类型（显然，m，n，k需要在运行时由用户给出；示例数据库包含的是33选6的10年间的所有数据）彩票数据分析的程序，以完成两种类型的分析。请勿改动数据库。

可能涉及到的知识点：

面向对象、运算符重载、模板、STL容器与STL算法、字符串处理，文件处理。

难点：

全组合的算法。（提示：可以采用回溯法）

性能提示：

传统串行算法在玩法2中表现不佳。可以考虑算法的并行化。可以手工实现多线程，也可以使用OpenMP实现并行化。但是请注意OpenMP在某些编译器编译后不很稳定。请优先使用VC2010、GNU C++或者.NET的Task模型（使用.NET 4.5的Async模型更好）。

可移植性提示：

尽可能遵循ANSI/ISO C++标准，尽量减少对Windows的平台依赖性。比如在实现并行化时优先考虑使用OpenMP或者POSIX thread 线程库<pthread.h>，而非直接使用Win32 API来创建线程。

结果输出：

请将统计结果输出到CSV（Comma separated value files，逗号分隔数值文件）。形如：2007048, 02, 11, 12, 15, 17, 28为一行（一条记录）。另外还要求在控制台输出程序运行时间（以秒为单位，可以使用C标准库中的time()函数）。

执行样例：

注意：12秒为应用并行算法的时间。彩票数据库可以从http://www.wpbeta.org/data.rar下载。

编程, 排列组合

评分

参与人数 1	宅币 +10	收起理由
风音洛洛	+ 10	o(￣▽￣)ブ发糖

查看全部评分

相关帖子

签名被小宅喵吞掉了~~~~(>_<)~~~~

使用道具举报

悠↑梦晴の乱

签到天数: 1 天

连续签到: 1 天

[LV.1]初来乍到

132 主题	256 好友	7万积分

第四章

积分: 70136

发表于 2012-4-12 19:27:56 | 显示全部楼层

疼讯空间的图片是无法直接引用的。请重新编辑。建议另存为图片后上传至点点再贴过来

新宅在管理层逐渐取代元老，不是所有人都可以忍受基友逐渐离去的孤寂的

回复支持反对

使用道具举报

LonghronShen

该用户从未签到

10 主题	5 好友	1441 积分

Continue

积分: 1441

楼主| 发表于 2012-4-12 19:43:33 | 显示全部楼层

悠↑梦晴の乱发表于 2012-4-12 19:27

登录/注册后可看大图

疼讯空间的图片是无法直接引用的。请重新编辑。建议另存为图片后上传至点点再贴过来 ...

图片问题已经修复。谢谢提醒！我是从Word复制来的，竟然也不行……

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

删除菌

该用户从未签到

1 主题	15 好友	1万积分

第一章

积分: 13251

发表于 2012-4-12 22:10:44 | 显示全部楼层

12秒挺快啊，是不是主要开销在穷举全部组合了？
数据文件链接有问题。看不到数据，不过想来数据量应该不是很大吧

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

LonghronShen

该用户从未签到

10 主题	5 好友	1441 积分

Continue

积分: 1441

楼主| 发表于 2012-4-12 23:58:22 | 显示全部楼层

删除菌发表于 2012-4-12 22:10

登录/注册后可看大图

12秒挺快啊，是不是主要开销在穷举全部组合了？
数据文件链接有问题。看不到数据，不过想来数据量应该不是 ...

链接已修正！时间的确是花在了组合数计算了。

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

LonghronShen

该用户从未签到

10 主题	5 好友	1441 积分

Continue

积分: 1441

楼主| 发表于 2012-4-20 20:02:56 | 显示全部楼层

ferlansue 发表于 2012-4-20 14:03

登录/注册后可看大图

不是每一次都是等概率随机的么

都知道彩票是随机过程，没啥可以预测的，但是还是有很多人执迷不悟地相信彩票是可以预测的。所以才有了各种玩法。我这里只是借了彩票的背景，来出一个排列组合方面的题目。^_^

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

johnnyworm

该用户从未签到

0 主题	1 好友	3402 积分

序章

积分: 3402

发表于 2012-5-14 15:14:10 | 显示全部楼层

没看明白输出应该啥样……

签名被小宅喵吞掉了~~~~(>_<)~~~~

回复支持反对

使用道具举报

LonghronShen

该用户从未签到

10 主题	5 好友	1441 积分

Continue

积分: 1441

楼主| 发表于 2012-5-21 19:57:12 | 显示全部楼层

本帖最后由 LonghronShen 于 2012-5-21 20:02 编辑

时隔这么久，还是公布一份源码吧。我用C#又写了一份未优化的版本，仅供参考。

[mw_shl_code=csharp,true]// ClassHelper.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Lottery
{

public static class Extension
{

      public static void SetValue<T>(this T[] source, T value1, T value2, int count, int startIndex = 0, int endIndex = Int32.MaxValue)
      {
         if (source.IsReadOnly == false)
         {
            if (endIndex == Int32.MaxValue)
                  endIndex = source.Length - 1;
            if (count <= 0 || count > endIndex - startIndex + 1)
                  return;
            int c = 1;
            for (int i = startIndex; i <= endIndex; i++)
            {
                  if (c <= count)
                     source = value1;
                  else
                     source = value2;
                  c++;
            }
         }
         else
         {
            throw new ArgumentException("The collection is read-only.");
         }
      }

      public static int CompareTo<T>(this IList<T> source, IList<T> other, bool sequencial = false)
      {
         if (sequencial)
         {
            if (source.Count == other.Count)
            {
                  int count = 0;
                  for (int i = 0; i < source.Count; i++)
                  {
                     if (source.Equals(other))
                        count++;
                  }
                  return count;
            }
            else
                  return -1;
         }
         else
         {
            int count = 0;
            for (int i = 0; i < source.Count; i++)
            {
                  if (other.Contains(source))
                     count++;
            }
            return count;
         }

      }

}

public static class Helper
{

      /// <summary>
      /// Get all combinations by your parameters.
      /// </summary>
      /// <param name="m"></param>
      /// <param name="k"></param>
      /// <returns></returns>
      public static List<List<int>> Combination(int m, int k)
      {
         List<List<int>> lst = new List<List<int>>();
         var ba = new bool[m];

         ba.SetValue(true, false, k);

         bool flag = true;

         do
         {
            var p = new List<int>();
            for (int i = 0; i < ba.Length; i++)
            {
                  if (ba == true)
                     p.Add(i + 1);
            }
            lst.Add(p);
            if (flag == false) break;
            for (int i = 0; i < ba.Length; i++)
            {
                  if (i + 1 <= ba.Length - 1)
                  {
                     if (ba == true && ba[i + 1] == false)
                     {
                        ba = false;
                        ba[i + 1] = true;
                        var count = (from b in ba.Take(i) where b == true select b).Count();
                        ba.SetValue(true, false, count, 0, i - 1);
                        break;
                     }
                  }
            }
            var lastZero = ba.ToList().LastIndexOf(false);
            if (lastZero >= ba.Length - k)
                  flag = true;
            else
                  flag = false;
         } while (true);

         return lst;
      }

}

}
[/mw_shl_code]

[mw_shl_code=csharp,true]// ClassRecord.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Lottery
{

public class Record
      : IComparable<Record>
{

      public string ID { get; set; }
      public List<int> Elements { get; private set; }
      public int[] Same { get; private set; }

      /// <summary>
      /// Indexer.
      /// </summary>
      /// <param name="index"></param>
      /// <returns></returns>
      public int this[int index]
      {
         get
         {
            if (index >= 0 && index < this.Elements.Count)
                  return this.Elements[index];
            else
                  throw new IndexOutOfRangeException("");
         }
      }

      public Record()
      {
         this.Elements = new List<int>();
         this.Same = new int[0];
      }

      /// <summary>
      /// Initialize the object by parsing the given line string.
      /// </summary>
      /// <param name="line"></param>
      public Record(string line)
      {
         this.Elements = new List<int>();
         var nums = line.Split(' ');
         this.ID = nums[0].Trim();
         for (int i = 1; i < nums.Length; i++)
         {
            this.Elements.Add(Int32.Parse(nums.Trim()));
         }
         this.Same = new int[this.Elements.Count + 1];
         for (int i = 0; i < this.Same.Length; i++)
         {
            this.Same = 0;
         }
      }

      /// <summary>
      /// Initialize the object by parsing the given posibility.
      /// </summary>
      /// <param name="p"></param>
      public Record(IList<int> p)
      {
         this.Elements = new List<int>(p);
         this.Same = new int[this.Elements.Count + 1];
         for (int i = 0; i < this.Same.Length; i++)
         {
            this.Same = 0;
         }
      }

      public int GetSimilarity()
      {
         for (int i = this.Elements.Count - 1; i >= 0; i--)
         {
            if (this.Elements != 0)
                  return i;
         }
         return -1;
      }

      /// <summary>
      /// Overload the equal operator.
      /// </summary>
      /// <param name="a"></param>
      /// <param name="b"></param>
      /// <returns></returns>
      public static bool operator ==(Record a, Record b)
      {
         if (a.Elements.Count != b.Elements.Count)
            return false;
         else
         {
            for (int i = 0; i < a.Elements.Count; i++)
            {
                  if (a != b)
                     return false;
            }
            return true;
         }
      }

      /// <summary>
      /// Overload the not equal operate.
      /// </summary>
      /// <param name="a"></param>
      /// <param name="b"></param>
      /// <returns></returns>
      public static bool operator !=(Record a, Record b)
      {
         return !(a == b);
      }

      /// <summary>
      /// Implement CompareTo function of IComparable<Record> interface.
      /// </summary>
      /// <param name="other"></param>
      /// <returns></returns>
      int IComparable<Record>.CompareTo(Record other)
      {
         return this.Elements.CompareTo(other.Elements, false);
      }

      public override bool Equals(object obj)
      {
         if (obj.GetType() == typeof(Record))
            return this == (obj as Record);
         else
            return false;
      }

      public override int GetHashCode()
      {
         return base.GetHashCode();
      }

      public override string ToString()
      {
         string result = "";
         foreach (int item in this.Elements)
         {
            result += item.ToString("D2") + "  ";
         }
         result += "-  ";
         if (this.Same.Length > 0)
         {
            foreach (int item in this.Same)
            {
                  result += item.ToString("D3") + "  ";
            }
         }
         return result.Trim();
      }

}

}
[/mw_shl_code]
[mw_shl_code=csharp,true]// Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Lottery
{
class Program
{

      static void Main(string[] args)
      {
         var t1 = DateTime.Now;

         Console.WriteLine("Please input the m value:");
         int m = Int32.Parse(Console.ReadLine());

         Console.WriteLine("Please input the n value:");
         int n = Int32.Parse(Console.ReadLine());

         Console.WriteLine("Please input the k value:");
         int k = Int32.Parse(Console.ReadLine());

         var lst = new List<Record>();
         using (System.IO.TextReader tr = new System.IO.StreamReader("data.txt", true))
         {
            var lines = tr.ReadToEnd().Split(new char[] { '\n' }, StringSplitOptions.RemoveEmptyEntries);
            foreach (var line in lines)
            {
                  lst.Add(new Record(line));
            }
         }

         Record result1 = lst[0];
         foreach (var item in lst)
         {
            foreach (var other in lst)
            {
                  if (item != other)
                  {
                     item.Same[item.Elements.CompareTo(other.Elements, false)]++;
                  }
            }
            if (item.GetSimilarity() > result1.GetSimilarity())
            {
                  result1 = item;
            }
            else
            {
                  if (item.GetSimilarity() == result1.GetSimilarity() && item[item.GetSimilarity()] > result1[result1.GetSimilarity()])
                  {
                     result1 = item;
                  }
            }
         }

         Console.WriteLine(String.Format("Result1 is: {0}.", result1.ToString()));

         var cb = Helper.Combination(m, k);
         var result2 = new List<Record>();
         using (System.IO.TextWriter tw = new System.IO.StreamWriter("Result2.txt", false))
         {
            for (int i = 0; i < cb.Count - 1; i++)
            {
                  var item = new Record(cb);
                  for (int j = 0; j < lst.Count; j++)
                  {
                     item.Same[item.Elements.CompareTo(lst[j].Elements, false)]++;
                  }
                  result2.Add(item);
                  tw.WriteLine(item.ToString());
            }
         }

         var t2 = DateTime.Now;

         Console.WriteLine(String.Format("Time elapsed: {0}", (t2 - t1).TotalSeconds.ToString()));
         Console.ReadKey(false);
      }

}

}
[/mw_shl_code]