‹‹ 上一主题 | 下一主题 ››
发新话题
打印

整数映射到排列的算法

admin

管理员

Rank: 9Rank: 9Rank: 9

帖子
1384 
精华
8 
积分
8014 
金钱
5726  
在线时间
380 小时 
注册时间
2007-4-18 
1# 大 中 小 发表于 2007-12-1 08:59  只看该作者

整数映射到排列的算法

//直接复制粘贴下来就能跑的

using System;
using System.Collections.Generic;
using System.Text;

namespace IntToP
...{
    class Program
    ...{
        //阶乘映射

static
ulong[] Jc;

        //结果演示，重在说明整数到排列的映射，遍历全排列不是重点

static
void Main(string[] args)
        ...{
            //计算阶乘，映射时会用到
            Jc = MakeJc();
            //这个值最大可以到20，表示最多演示多少个元素的排列

int nMax =
5;
            //表示排列的数组，用于承载排列结果

byte[] dict =
new
byte[nMax];

            for (int n =
3; n <=
5; ++n)
            ...{
                Console.WriteLine("{0}个元素时，数值映射到排列的情况",n);
                for (ulong idx =
0; idx < Jc[n]; ++idx)
                ...{
                    //计算(idx,n)对应的排列
                    computeDict(idx,dict, n);
                    //显示结果
                    Console.Write(string.Concat(idx.ToString(), ":"));
                    for (int i = n; --i >=
0; )
                    ...{
                        Console.Write('
');
                        Console.Write(dict);
                    }
                    Console.WriteLine();
                }
            }

            Console.ReadLine();
        }
        /**////
<summary>
        /// 把整数映射到排列，这个是核心
        ///
</summary>
        ///
<param name="index">要映射成排列的整数，排列的序号</param>
        ///
<param name="outDict">用于承载排列结果的数组</param>
        ///
<param name="len">排列的长度，表示是几个元素的排列</param>


private
static
void computeDict(ulong index,byte[] outDict, int len)
        ...{
            for (int i = len; --i >=
0; )
            ...{
                outDict =
0;
            }

           
            index %= Jc[len];
            for (int i = len -
1; i >=
0; --i)
            ...{
                outDict = (byte)(index / Jc);
                index %= Jc;
            }

            for (int i =
1; i < len; ++i)
                for (int j =
0; j < i; ++j)
                    if (outDict <= outDict[j])
                    ...{
                        ++outDict[j];
                    }
        }
        /**////
<summary>
        /// 计算阶乘，可以忽视
        ///
</summary>
        ///
<returns>返回包换了阶乘映射的数组</returns>


private
static
ulong[] MakeJc()
        ...{
            ulong[] result =
new
ulong[21];//0 to 20
            result[0] = result[1] =
1;
            for (ulong i =
2; i <
21; ++i)
            ...{
                result = result[i -
1] * i;
            }
            return result;
        }
    }
}

TOP

‹‹ 上一主题 | 下一主题 ››
发新话题