list manipulation - How to construct tuples with a given order?

How do I create a list of tuples with an ordering imposed on them, where each element is from a generating set? Specifically, I'm trying to create a listing of tuples $(x_1, x_2, ..., x_n)$ such that $x_1 > x_2$, $x_2 \leq x_3 \leq \cdots x_n$ where each $x_i$ is in (say) $X = \{a,b,c,d\}$. The elements of $X$ are in lexicographic order.

Code:

rank = 4;
weight = 3;

X = Range[rank]; 
bc = Tuples[X, weight];
Cases[bc, {x1_, x2_, x3_} /; x1 > x2 && x2 <= x3]

Issues 1. rank and weight are independent; they don't need to be =. 2. I'd like to say x1_, .., xrank_, but I'm not sure how to specify x_rank. Also x2 <= x3 <= ... <= xrank. (I'll loop on rank and weight, so these won't be hard-coded values.) 3. At the end, 1, 2, ..., rank should be traded for a, b, ... (whatever letter).

Answer

If I understand the question generating all Tuples and then filtering is wasteful, and will "blow up" for long sets. Since you want all but one element in canonical order I believe you should generate those, then prefix as needed to complete the sequence.

Here is a mundane loop-based way to build the tuples; I couldn't think of anything that ran faster.

tuples[rank_Integer, k_Integer] :=
  Block[{i},
    i[0] = 1;
    Flatten[
      Table @@ Join[{First /@ #}, #] &@Array[{i[#], i[# - 1], rank} &, k - 1],
      k - 2
    ]
  ] // Join @@ (Table[{i, ##}, {i, # + 1, rank}] & @@@ #) &

Example:

tuples[5, 3]

{{2, 1, 1}, {3, 1, 1}, {4, 1, 1}, {5, 1, 1}, {2, 1, 2}, {3, 1, 2}, {4, 1, 2}, {5, 1, 2},
 {2, 1, 3}, {3, 1, 3}, {4, 1, 3}, {5, 1, 3}, {2, 1, 4}, {3, 1, 4}, {4, 1, 4}, {5, 1, 4},
 {2, 1, 5}, {3, 1, 5}, {4, 1, 5}, {5, 1, 5}, {3, 2, 2}, {4, 2, 2}, {5, 2, 2}, {3, 2, 3},
 {4, 2, 3}, {5, 2, 3}, {3, 2, 4}, {4, 2, 4}, {5, 2, 4}, {3, 2, 5}, {4, 2, 5}, {5, 2, 5},
 {4, 3, 3}, {5, 3, 3}, {4, 3, 4}, {5, 3, 4}, {4, 3, 5}, {5, 3, 5}, {5, 4, 4}, {5, 4, 5}}

You can fill these tuples with arbitrary expressions like this:

x = {"a", "b", "c", "d", "e"};

x[[#]] & /@ tuples[5, 3]

{{"b", "a", "a"}, {"c", "a", "a"}, {"d", "a", "a"}, . . .
   {"e", "c", "e"}, {"e", "d", "d"}, {"e", "d", "e"}}

The function will work on values that would not work with Tuples:

tuples[12, 8] // Length

306306

Using Tuples before filtering would generate 12^8 = 429,981,696 sets.