Native apps are back on the menu!

A few months ago, Rudy Huyn, a Partner Architect at Microsoft working on the Store and File Explorer, officially confirmed that Microsoft plans to build 100% native apps for Windows 11.

This stems from the fact, that Microsoft used React Native in their taskbar.

Users on the social platform X have identified performance problems linked to the Windows 11 Start Menu, noting that the component utilizes React Native.

From Microsoft:

Satya Nadella, Chairman and CEO, shared the below communication with Microsoft employees. [...] Today, I want to talk about something critical to our company’s future: prioritizing security above all else.

In the meantime, we'll keep an eye on the CVE dataset.

If you're running Ableton Live 11 on Linux via Wine, you may have encountered black rectangles all over the place, or even the whole screen is flickering.

The following option fixed it for Ableton and the Plugins "Saturn" and "Fabfilter". But "Serum" is still affected. Maybe Serum uses a different GUI rendering backend.

Solution

1. cd ~/.wine/drive_c/users/{user}/AppData/Roaming/Ableton/Live 11.3.42/Preferences/
2. create a new file: options.txt
3. Append the line: -_ForceGdiBackend

I don't know if the following information is relevant for you, but this is my systems overview:

• Arch Linux
• X11
• Nvidia RTX 2070 Super
• wine-staging
• winecfg: added library "dxgi (native, builtin)"

I hope it helped :)

We're answering two questions:

• How does the Steinhaus-Johnson-Trotter algorithm works?
• And how to implement it in Rust

The language doesn't matter. I've only choosen Rust, because I'm currently on my Rust arc.

The algorithm can be implemented by recursion, or by iteration. I'm covering the iterative approach, because - for me - it's easier to reason about it.

Let's dive in

Primer

Short primer what a permutation of a set is:
Assume we have the set (1, 2, 3). The permutation of this would be all the possible positional combinations of the members.

For example:

P1 -> 1 2 3
P2 -> 1 3 2
P3 -> 3 1 2
P4 -> 3 2 1
P5 -> 2 3 1
P6 -> 2 1 3

Side note: The factorial of the size of the set represents the maximum permutation:

len(permutate(1, 2, 3)) == factorial(len((1, 2, 3)))

SJT explained

In SJT, integers are bound to "directions", where they can point to the left or right.
At initialization, all integers are pointing to the left, like that:

<1 <2 <3

And under certain conditions (described down below), they can reverse the direction:

3> <2 <1

Those integers are defined as "mobile integers".

Definition: Mobile Integer

A mobile integer is ...

1. able to swap positions with its adjacent integer
2. not pointing to an edge
3. greater than the integer it points to

An edge is defined as the "end" of a set:

 Edge
 v
 | <1 <2 <3 |
            ^
            Edge

And given this constellation:

<2 <1 3>

There are no mobile integers, since:

• "2" points to an edge (Rule 2)
• "1" is not greater than the integer it points to (Rule 3)
• "3" points also to an edge

Basic Algorithm

1. Find largest mobile integer (k)
2. Swap the position of (k) with the integer, it points to
3. Reverse the direction of all integers that are greater than (k)

Exit rule: If there are no mobile integers, the algorithm is done

Example (Step by Step)

The following example is split into each permutation step. P<number> indicates the current permutation.
And (Step n) corresponds to the steps from the paragraph Basic Algorithm.

Init    <1  <2  <3      // initialize the direction of all integers, so they're pointing to the left

P1      <1  <2  <3      // (Step 1) find the highest mobile integer, which is "3"

P2      <1  <3  <2      // (Step 2) swap positions
        <1  <3  <2      // (Step 3) since there's no integer larger than (k), we skip this step
        <1  <3  <2      // (Step 1) again; "3" is the largest mobile integer

P3      <3  <1  <2      // (Step 2) swap again
        <3  <1  <2      // (Step 3) no greater integer than (k), we skip it again
        <3  <1  <2      // (Step 1) "3" isn't mobile, since it points to an edge. So we take "2"

P4      <3  <2  <1      // (Step 2) swap "2" with "1"
         3> <2  <1      // (Step 3) "3" is larger than (k), so we reverse the direction of "3"
         3> <2  <1      // (Step 1) since (Rule 3) of the definition, only "3" complies with the definition

P5      <2   3> <1      // (Step 2) "3" pointed to the right, so it swaps positions with "2"
        <2   3> <1      // (Step 3) there's no integer larger than (k)
        <2   3> <1      // (Step 1) "3" is the largest mobile integer again. 
                        //          Since "2" points to an edge, and "1" points to an larger integer

P6      <2  <1   3>     // (Step 2) swap "3" with "1"
        <2  <1   3>     // (Step 3) there's no larger integer than (k), so we skip again
        <2  <1   3>     // (Step 1) there's no mobile integer anymore, because 
                        //          "2" & "3" are pointing to an edge; "1" points to an larger number

End                     // And without any mobile integers, the algorithm is terminated

Credits to cut-the-knot.org which helped me a lot, to understand the algorithm.

Implementation

We're walking through the full implementation step by step. You can view the Complete Implementation.

It is important to mention, that the following function is meant to generate permutations for vector indexing.

$ foo = ["A", "B", "C"]
$ apply_permutation_on_index(foo)
[["A", "B", "C"], ["A", "C", "B"], ["C", "A", "B"], ...]

Thats the reason why the function only takes one parameter, and assumes 0..n.

So adapt it to your personal needs.

Function Signature

 1  fn permutation(n: usize) -> Vec<Vec<usize>> {

For example you want the permutations of (0, 1, 2):
With n you declare the size of the set. If you provide 3, it will generate (0, 1, 2).
Regarding the return type, it depends on your use case. So you might want a different return type for your project.

Side note: I'm sticking to the word "set" to be consistent - although the structure in Rust is a vector.

In this walkthrough, we declare that n = 3.

Initialization

 2      let mut perm: Vec<usize> = (0..n).collect();    // generating the "set"
 3      let mut direction: Vec<i32> = vec![-1; n];      // initialize a vector with -1, which represents 
                                                        //     the direction of the values in `perm`

 4      let mut result: Vec<Vec<usize>> = Vec::new();   // the permutated values will be stored here
 5
 6      let factorial = (1..=n).product();  // calculating the max possible permutation steps,
                                            // so we can use it as an upper bound for the loop
 7
 8      result.push(perm.clone());  // storing the first permutation

At line 3 we created a structure, that looks like this: [-1, -1, -1].
The negative sign indicates, that the mobile integer is pointing to the left.
If there's no sign, then the mobile integer points to the right.

Loop: Inner Loop

10      for _ in 0..factorial {
11          let mut mobile_index = None;
12
13          for i in 0..n {
14              if (direction[i] == -1 && i > 0 && perm[i] > perm[i - 1])
15                  || (direction[i] == 1 && i < n - 1 && perm[i] > perm[i + 1])
16              {
17                  if mobile_index.is_none() || perm[i] > perm[mobile_index.unwrap()] {
18                      mobile_index = Some(i);
19                  }
20              }
21          }

At line 10 we're looping 5 times: for _ in 0..6.

But why only five times? Since the maximum permutation step is 3! == 6?
Because we already saved the first permutation at line 8.

At line 11 our mobile_index represents (k), as described in the paragraph Basic Algorithm.

The inner loop at line 13 resolves into for i in 0..3, which corresponds to our "set" of 0, 1, 2

At line 14 & 15 we have a few conditions. To make this easier, we look into the first iteration, where i = 0:

// i = 0; n = 3

if (direction[i] == -1          // IF  the direction of `i` points to the left
    && i > 0                    // AND `i` is greater than 0 (our leftmost edge)
    && perm[i] > perm[i - 1])   // AND the current mobile integer of our "set" is greater than the left one
    
    || (direction[i] == 1       // OR  the direction of `i` points to the right
    && i < n - 1                // AND `i` is smaller than the maximum integer in the "set"
    
                                // Side note: Since `0..n` is non-inclusive, we have to subtract by one, 
                                //            to get the correct integer in the loop 
                                
    && perm[i] > perm[i + 1])   // AND the current mobile integer is greater than the right one

Since the condition will short-circuit to false, because 0 > 0 == false, it will skip the inner if block, and continue further.

Basically, this if block evaluates the rules from the paragraph Basic Algorithm, and searches for a mobile integer.
Let's proceed with the inner if block. Where we assume i = 1:

// i = 1

if mobile_index.is_none()                       // IF mobile_index contains no value
    || perm[i] > perm[mobile_index.unwrap()] {  // OR the current mobile integer is 
                                                //    greater than last mobile integer
                                                
    mobile_index = Some(i);                     // Store the current mobile integer

Since mobile_index contains no value, we store 1 in it. The next iteration will be i = 2, and it will overwrite the mobile_index value. Which now proceeds further ahead.

Loop: Swaps

23          let mobile_index = match mobile_index {
24              Some(index) => index,
25              None => break,
26          };
27
28          let new_index = (mobile_index as isize + direction[mobile_index] as isize) as usize;
29          perm.swap(mobile_index, new_index);
30          direction.swap(mobile_index, new_index);

At line 23 - 26 we got the exit condition, as described in Basic algorithm.
When there's no mobile index, it breaks the outer loop and returns the result.

At line 28, the code can be broken down to: new_index = mobile_index + direction[mobile_index].
If we assume mobile_index = 2, the variable results into: new_index = 2 + -1 -> new_index = 1.

After that, in line 29 & 30, we perform the swaps:

// pre swap:
//     perm = [0, 1, 2]
//     direction = [-1, -1, -1]

perm.swap(2, 1);
direction.swap(2, 1);

// post swap:
//     perm = [0, 2, 1]
//     direction = [-1, -1, -1]

The perm and direction structures are tied together, so we have to modify both.

Loop: Reverse Direction

32          let moved_value = perm[new_index];
33
34          for i in 0..n {
35              if perm[i] > moved_value {
36                  direction[i] *= -1;
37              }
38          }
39          result.push(perm.clone());

In this section, we have to evaluate, if there are any directions to reverse.

At line 32 we store the current position of the mobile integer (k). Following with a comparison, if there's any integer higher than (k), we reverse the direction of the affected integers.

Finally, we append the current permutation to our result vector. And if the exit condition is met, if will return the final value.

Note on this Implementation

This implementation is not optimized, since there are a few clone() scattered around, and might degrade performance.
And I somehow have the gut feeling, that this can be solved without an additional direction vector. But this may be a task for a different day.

Complete Implementation

 1  fn permutation(n: usize) -> Vec<Vec<usize>> {
 2      let mut perm: Vec<usize> = (0..n).collect();
 3      let mut direction: Vec<i32> = vec![-1; n];
 4      let mut result: Vec<Vec<usize>> = Vec::new();
 5
 6      let factorial = (1..=n).product();
 7
 8      result.push(perm.clone());
 9
10      for _ in 0..factorial {
11          let mut mobile_index = None;
12
13          for i in 0..n {
14              if (direction[i] == -1 && i > 0 && perm[i] > perm[i - 1])
15                  || (direction[i] == 1 && i < n - 1 && perm[i] > perm[i + 1])
16              {
17                  if mobile_index.is_none() || perm[i] > perm[mobile_index.unwrap()] {
18                      mobile_index = Some(i);
19                  }
20              }
21          }
22
23          let mobile_index = match mobile_index {
24              Some(index) => index,
25              None => break,
26          };
27
28          let new_index = (mobile_index as isize + direction[mobile_index] as isize) as usize;
29          perm.swap(mobile_index, new_index);
30          direction.swap(mobile_index, new_index);
31
32          let moved_value = perm[new_index];
33
34          for i in 0..n {
35              if perm[i] > moved_value {
36                  direction[i] *= -1;
37              }
38          }
39          result.push(perm.clone());
40      }
41      result
42  }

If you're cross compiling with Rust, you're possibly using Cross.

In some projects, you might encounter an error message regarding missing libssl.
For example:

Could not find directory of OpenSSL installation [...]

The (to me) cleanest solution is, to create a Cross.toml file in your project root dir, and declare the libssl installation for each target.

Example:

[target.x86_64-unknown-linux-gnu]
pre-build = [
    "apt update",
    "apt install libssl-dev -y"
]

[target.aarch64-unknown-linux-gnu]
pre-build = [
  "dpkg --add-architecture $CROSS_DEB_ARCH", 
  "apt-get update && apt-get --assume-yes install libssl-dev:$CROSS_DEB_ARCH"
]

I do not know where I found this solution. Somewhere deep in the web, buried between some dirty hacks. But this solved, at least, my problem.