Sage：迭代增加序列

Question

我有一个问题，我不愿意相信在Sage中没有解决过。

给定长度的所有非降序列d其所有条目的一对整数（d，n）的作为输入，我想接收的列表（或设置，或其他）不大于n。

类似地，我想返回所有严格递增长度d的序列，其条目是不大于Ñ另一功能。

例如，对于d = 2n = 3的，身份证接收输出：

[[1,2]，[1,3]，[2,3]]

或

[[1,1]，[1,2]，[1,3]，[2,2]，[2,3]，[3,3]]

取决于关于我是使用增加还是减少。

有谁知道这样的功能？

编辑当然，如果有这样一种不增加或减少序列的方法，我可以修改它以符合我的目的。只是一些重复序列

Answer 1

这个问题可以通过使用此处描述的类 “UnorderedTuples” 来解决：

http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tuple.html

要使用的条目返回0和长度d的n-1个之间的所有一切非降序列，你可以键入：

UnorderedTuples(range(n),d) 

这将返回非递减序列作为列表。我需要一个不可变的对象（因为序列将成为字典的关键字）。所以我用“元组”的方法把列表变成元组：

immutables = [] 
for s in UnorderedTuples(range(n),d): 
    immutables.append(tuple(s)) 
return immutables 

而且我也写了挑选出只有增加序列的方法：

def isIncreasing(list): 
    for i in range(len(list) - 1): 
     if list[i] >= list[i+1]: 
      return false 
    return true 

只有一个返回的方法严格递增序列看起来像

immutables = [] 
for s in UnorderedTuples(range(n),d): 
    if isIncreasing(s): 
     immutables.append(tuple(s)) 
return immutables 

Answer 2

这可能不是一个很好的回答你的问题。但原则上，您可以使用Partitions和max_slope=-1参数。随着过滤列表IntegerVectors听起来同样效率低下，并出于其他原因压抑。

如果它有一个规范的名字，它可能在sage-combinat功能列表中，甚至有一个基类可以用于integer lists，这基本上就是你在问什么。也许你可以用IntegerListsLex得到你想要的东西？希望这证明有帮助。

Answer 3

我也需要这个算法，我终于设法写一个今天。我会在这里分享代码，但是我上周才开始学习代码，所以不太好。

想法输入=（r，d）。步骤1）创建一个包含数组Integer [r + 1]的列表L的类“ListAndPosition”，以及一个介于0和r之间的整数q。步骤2）创建一个接收ListAndPosition（L，q）的方法，并依次筛选L中的数组，检查位置q上的整数是否小于位置q + 1上的整数，如果是，则它会添加一个新数组列表的底部与该条目++。完成后，方法再次使用新列表和q-1作为输入进行自我调用。

步骤1）的代码

import java.util。数组列表;

public class ListAndPosition {public static Integer r = 5;

public final ArrayList<Integer[]> L; 
public int q; 

public ListAndPosition(ArrayList<Integer[]> L, int q) { 
    this.L = L; 
    this.q = q; 
} 
public ArrayList<Integer[]> getList(){ 
    return L; 
} 
public int getPosition() { 
    return q; 
} 
public void decreasePosition() { 
    q--; 
} 
public void showList() { 
    for(int i=0;i<L.size();i++){ 
     for(int j=0; j<r+1 ; j++){ 
      System.out.print(""+L.get(i)[j]); 
     } 
     System.out.println(""); 
    } 
} 

}

用于步骤2）

进口java.util.ArrayList中的代码;

公共类NonDecreasingSeqs {

public static Integer r=5; 
public static Integer d=3; 

public static void main(String[] args) { 

    //Creating the first array 

    Integer[] firstArray; 
    firstArray = new Integer[r+1]; 
    for(int i=0;i<r;i++){ 
     firstArray[i] = 0; 
    } 
    firstArray[r] = d; 

    //Creating the starting listAndDim 
    ArrayList<Integer[]> L = new ArrayList<Integer[]>(); 
    L.add(firstArray); 

    ListAndPosition Lq = new ListAndPosition(L,r-1); 

    System.out.println(""+nonDecSeqs(Lq).size()); 

} 

public static ArrayList<Integer[]> nonDecSeqs(ListAndPosition Lq){ 

    int iterations = r-1-Lq.getPosition(); 
    System.out.println("How many arrays in the list after "+iterations+" iterations? "+Lq.getList().size()); 

    System.out.print("Should we stop the iteration?"); 

    if(0<Lq.getPosition()){   
     System.out.println(" No, position = "+Lq.getPosition()); 

     for(int i=0;i<Lq.getList().size();i++){ 
      //Showing particular array 
      System.out.println("Array of L #"+i+":"); 
      for(int j=0;j<r+1;j++){ 
       System.out.print(""+Lq.getList().get(i)[j]); 
      } 

      System.out.print("\nCan it be modified at position "+Lq.getPosition()+"?"); 

      if(Lq.getList().get(i)[Lq.getPosition()]<Lq.getList().get(i)[Lq.getPosition()+1]){ 
       System.out.println(" Yes, "+Lq.getList().get(i)[Lq.getPosition()]+"<"+Lq.getList().get(i)[Lq.getPosition()+1]); 

       { 
        Integer[] tempArray = new Integer[r+1]; 
        for(int j=0;j<r+1;j++){ 
         if(j==Lq.getPosition()){ 
          tempArray[j] = new Integer(Lq.getList().get(i)[j])+1; 
         } 
         else{ 
          tempArray[j] = new Integer(Lq.getList().get(i)[j]); 
         } 
        } 
        Lq.getList().add(tempArray); 
       } 
       System.out.println("New list");Lq.showList(); 
      } 

      else{ 
       System.out.println(" No, "+Lq.getList().get(i)[Lq.getPosition()]+"="+Lq.getList().get(i)[Lq.getPosition()+1]); 
      } 
     } 
     System.out.print("Old position = "+Lq.getPosition()); 
     Lq.decreasePosition(); 
     System.out.println(", new position = "+Lq.getPosition()); 

     nonDecSeqs(Lq); 
    } 
    else{ 
     System.out.println(" Yes, position = "+Lq.getPosition()); 
     } 
    return Lq.getList(); 
} 

}

备注：我需要我序列以从0开始，并在d结束。