How are constructs with data-dependent swaps and rotations cryptanalyzed? Linear and differential cryptanalysis seem well suited for constructs with a (relatively) simple fixed structure of boolean expressions. But some ciphers incorporate swaps of array elements where the indices to be swapped are dependent on dynamic cipher state and others may include rotations by a variable number of bits. In the case of RC4, the entire cipher state is embodied in the permutation of a fixed set of integers.

This would seem to induce a combinatorial explosion in the number of expressions needed to track bias through the system. Is that a good thing?

Side-channel challenges aside, are such constructs unambiguously stronger than those made from fixed structures, or are they just harder to analyze?

What math is used to attack/analyze them?
Algorithms which swap bytes in an array are notoriously hard to analyze; the two main examples are RC4 (encryption) and MD2 (hashing). Being "hard to analyze" does not mean that they are strong; only that we do not have a generic framework such as differential cryptanalysis to apply to them. Both RC4 and MD2 are, academically speaking, "broken" (there are known attacks which are at least theoretically faster than what would be expected from the key/output length). Cryptanalysis is "ad hoc". For instance, in the case of RC4, the main result is due to Mantin and Shamir: they show that the probability of the second output byte of a RC4 stream to be 0 is about twice what it should be (1/128 instead of 1/256). The mathematics are elementary: they simply follow the algorithm description.

Being hard to analyze is not a good thing. It may slow down an attacker, but it also prevents algorithm designers from working efficiently. Simple, regular structures are preferred: we do not want algorithms that are just difficult to break; we want algorithms that we know are difficult to break.

Also, a RAM-based structure with a mutable array implies heavy implementation costs on very small architectures (smartcards, where RAM is the scarcest resource) and on dedicated circuits (FPGA, ASIC). On a PC, RAM access is relatively fast, but still not as fast as one could hope for. MD2 is known to be very slow and RC4 is outperformed by more recent stream ciphers. Hardness of analysis and performance issues make mutable arrays unpopular in recent algorithm designs.