首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在给定两个n元组的情况下,如何有效地实现/构造以下排列?

在给定两个n元组的情况下,如何有效地实现/构造以下排列?
EN

Stack Overflow用户
提问于 2011-11-16 02:08:19
回答 1查看 145关注 0票数 1

我正在学习排队论,在这个理论中,我经常遇到以下情况。

设x,y都是非负整数的n元组(描述n个队列的长度).此外,x和y都有称为“主队列”的区分队列。例如,

X= 3,6,1,9,5,2与x‘=1

Y= 6,1,5,9,5与y‘=5

(根据Python的术语,我正在计算队列0-5。)

如何有效地在{0,1,...,5}上实现/构造以下置换f?

  1. 第一次设f(x') =y。在这里,f(1) =5,

  1. ,然后对任意i设f(i) =i,使得xi == yi。显然,没有必要考虑指数x‘和y’。在这里,f(3) =3(都长9)和f(4) =4(都长5)。
  2. 现在有相同大小的队列集,在x和y中没有配对。所以在x中,这是{0,2,5},在y中是{0,1,2}。
  3. 将这些队列从1到s排序,其中s是集合的公共大小,长度为1 ==最低秩==最短队列和s ==最高秩==最长队列。因此,在这里,s= 3,在x秩(0)= 1,秩( 2 )= 3,秩(5)= 2,在y秩(0)= 1,秩(1)=3,秩(2)=2。如果有领带,则给具有较大索引的队列以更高的秩。
  4. 将这些队列按秩分开。这里f(0) = 0,f(2) = 1,f(5) = 2.

这将给出置换0,5,1,3,4,2。

我的解决方案包括多次跟踪x和y上的索引和循环,而且效率很低。(大致查看我的应用程序中的n >= 1,000,000 )。

任何帮助都将不胜感激。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2011-11-16 02:39:32

因为你必须做排名,你不能得到线性和需要排序。所以看起来很简单。在O( 1 )中做1,在O(n)中做2,只需遍历n元组。同时,您可以构造x和y的副本,只包含3的副本,但不只是包含值,而是使用原值的元组及其索引。

在你的例子中,x和元组左是[3,0,1,2,2,5],y-与-元组-左是[6,0,1,1,5,2]。

然后对x与元组左和y与元组左(它将是O(n.log n))进行排序,并从相应元组的第二个元素中读取置换。

在你的例子中,排序x和.将是[1,2,2,5,3,0]并排序为y-.将是[1,1,5,2,6,0]。现在,从第二个元素中可以很好地看到5 : f(2)=1,f(5)=2,f(0)=0。

编辑:在Javascript中包括O(n+L):

代码语言:javascript
复制
function qperm (x, y, xprime, yprime) {
  var i;
  var n = x.length;
  var qperm = new Array(n);
  var countsx = [], countsy = []; // same as new Array()
  qperm[xprime] = yprime; // doing 1.

  for (i = 0; i < n; ++i) {
    if (x[i] == y[i] && i != xprime && i != yprime) { // doing 2.
      qperm[i] = i; }
    else { // preparing for 4. below
      if (i != xprime) {
        if (countsx[x[i]]) countsx[x[i]]++; else countsx[x[i]] = 1; }
      if (i != yprime) {
        if (countsy[y[i]]) countsy[y[i]]++; else countsy[y[i]] = 1; } }

  // finishing countsx and countsy
  var count, sum;
  for (i = 0, count = 0; i < countsx.length; ++i) {
    if (countsx[i]) {
      sum = count + countsx[i];
      countsx[i] = count;
      count = sum; }
  for (i = 0, count = 0; i < countsy.length; ++i) {
    if (countsy[i]) {
      sum = count + countsy[i];
      countsy[i] = count;
      count = sum; }

  var yranked = new Array(count);      
  for (i = 0; i < n; ++i) {
    if (i != yprime && (x[i] != y[i] || i == xprime)) { // doing 4. for y
      yranked[countsy[y[i]]] = y[i];
      countsy[y[i]]++; } }

  for (i = 0; i < n; ++i) {
    if (i != xprime && (x[i] != y[i] || i == yprime)) { // doing 4. for x and 5. at the same time
      // this was here but was not right: qperm[x[i]] = yranked[countsx[x[i]]];
      qperm[i] = yranked[countsx[x[i]]];
      // this was here but was not right: countsy[y[i]]++; } } }
      countsx[x[i]]++; } }

  return qperm; }

希望它是正确的;-)

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/8145777

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档