- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace _2Enumerable
- {
- class Program
- {
- static HashSet<List<int>> set = new HashSet<List<int>>();
- static void Main(string[] args)
- {
- var array = new List<int>() {7,6,5,4,3,2,1};
- array.ForEach(x => Console.WriteLine("{0}是夹数:{1}",x,IsJiaNum(x)));
- Console.WriteLine("输入一个数m,判断它是否为夹数:");
- int number;
- while (!int.TryParse(Console.ReadLine(), out number)) ;
- Console.WriteLine("{0}是夹数:{1}", number, IsJiaNum(number));
- Console.ReadKey();
- }
- //
- public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> collection) where T : IComparable
- {
- if (!collection.Any())
- {
- return new List<IEnumerable<T>>() {Enumerable.Empty<T>() };
- }
- var sequence = collection.OrderBy(s => s).ToArray();
- return sequence.SelectMany(s => GetPermutations(sequence.Where(s2 => !s2.Equals(s))).Select(sq => (new T[] {s}).Concat(sq)));
- }
- //给定自然数m,判断m是否满足:1到m各两对共2m个数字存在一个排列,使得每两个相等数字之间的间隔个数与自身相等。
- static bool IsJiaNum(int m)
- {
- List<int> numberPool = new List<int>();//存 1 - m 个2对共2m个数字
- for (int i = 1; i <= m; i++)
- {
- numberPool.Add(i);
- }
- set.Clear();
- var list = GetPermutations(numberPool);
- var enumerator = list.GetEnumerator ();
- while (enumerator.MoveNext()) {
- var item = enumerator.Current;
- //m elements and m 0s
- List<int> myitem = new List<int>(item);
- myitem.AddRange(new int[m]);
- //a list for checking first coming or second
- List<int> copy = new List<int>(item);
- for (int i = 0; i < 2*m; i++) {
- //items exceed 2m elements, discard this list.
- if(myitem[i]+i+1>=2*m)
- break;
- // if element comes secondly, go to next element
- if(copy.FindAll(u=>u==myitem[i]).Count==0)
- continue;
- //if items to insert are not slots, move that item to next and put it there.
- if(myitem[myitem[i]+i+1]!=0)
- {
- myitem.Insert(myitem[i]+i+1,myitem[i]);
- myitem.RemoveAt(myitem.Count-1);
- }
- else
- //if items to insert are slots, put it in the slot
- myitem[myitem[i]+i+1] = myitem[i];
- //remove element for checking if it is second
- copy.Remove(myitem[i]);
- }
- // if some slots exist, this list is skipped.
- var result = myitem.FindAll(u=> u ==0);
- if(result.Count>0)
- continue;
- // check the list again, because some list doesn't match the property.
- copy = new List<int>(item);
- for (int i = 0; i < 2*m; i++) {
- //second comes element, skip
- if(copy.FindAll(u=>u==myitem[i]).Count==0)
- continue;
- //if number doesn't match the property, skip the list.
- if(myitem[i]!=myitem[myitem[i]+i+1])
- break;
- //first chance is over.
- copy.Remove(myitem[i]);
- }
- if(copy.Count>0)
- continue;
- set.Add(myitem);
- }
- if (set.Count>0) {
- foreach (var item in set) {
- Console.WriteLine("{0}是夹数,并且该序列是:", m);
- item.ForEach(x => Console.Write(x + " "));
- Console.WriteLine();
- }
- return true;
- }
- return false;
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1409201513679.html
来源: http://www.codesnippet.cn/detail/1409201513679.html