Sage：遍历递增序列

Question

我有一个我不愿意相信以前在 Sage 中没有解决的问题。

给定一对整数 (d,n) 作为输入，我想接收所有 的列表（或集合，或其他）长度为 d 的非递减 序列，所有条目均不大于 n.

同样，我想要另一个函数，它 returns 所有 严格递增 长度为 d 的序列，其条目是 no大于 n.

例如，对于 d = 2 n=3，我会收到输出：

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

或

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

取决于我使用的是递增还是非递减。

有人知道这样的功能吗？

编辑当然，如果有这种非递增或递减序列的方法，我可以修改它以适合我的目的。只是迭代序列的东西

Answer 1

对于您的问题，这可能不是一个很好的答案。但原则上，您可以使用 Partitions 和 max_slope=-1 参数。由于其他原因，混杂 IntegerVectors 的过滤列表听起来同样低效且令人沮丧。

如果它有一个规范的名称，它可能会在 sage-combinat 功能列表中，甚至还有一个基础 class 可以用于 integer lists, which is basically what you are asking about. Maybe you could actually get what you want using IntegerListsLex？希望这对您有所帮助。

Answer 2

我也需要这个算法，今天终于写了一个。我将在这里分享代码，但我上周才开始学习编码，所以它并不漂亮。

想法输入=(r,d)。步骤 1) 创建一个 class "ListAndPosition"，它有一个数组列表 L，其中包含 Integer[r+1]'s，以及一个介于 0 和 r 之间的整数 q。 Step 2) 创建一个方法，接收一个ListAndPosition(L,q)并依次筛选L中的数组，检查位置q的整数是否小于位置q+1的整数，如果是，则在带有该条目 ++ 的列表底部。完成后，该方法再次调用自身并使用新列表和 q-1 作为输入。

步骤 1) 的代码

进口java.util.ArrayList;

public class ListAndPosition { public 静态整数 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;

public class 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 结束。

Answer 3

这个问题可以使用这里描述的 class "UnorderedTuples" 来解决：

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

要return 所有条目在 0 到 n-1 之间且长度为 d 的所有非递减序列，您可以键入：

UnorderedTuples(range(n),d)

这个return是列表形式的非递减序列。我需要一个不可变的对象（因为序列将成为字典的键）。所以我使用 "tuple" 方法将列表转换为元组：

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

return只严格增加序列的方法看起来像

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

Sage：遍历递增序列

Sage: Iterate over increasing sequences

sequence

sage