1
$\begingroup$

Note: I am searching for an algorithm that can do what I need or something similar to it, so that I can try to adapt it to my needs. My idea here was to ask for a reference (e.g. "This can be solved using an algorithm called xyz") but obviously I would also appreciate it if someone took the time to create one on-the-fly. The latter is not my expectation though. I am mostly looking for some keywords to continue my research on.


Algorithm description

I am searching for an algorithm that can bring a given set of elements as close to a different set of the same length as possible. However the tricky part is that only specific elements may be exchanged.

The elements in the set can be assumed to have an intrinsic order. That is we can define a series a < b < c < d < ... for all elements across the sets.

The allowed changes are not known beforehand but are generally in the form of "replace the i-th element in the set with the j-th one" or "Replace the i-th and the j-th element and at the same time the k-th with l-th" or any extension of that. Thus: Pairwise exchanges of one or more pairs of elements where not the element itself but its position within the set is important.

As an example consider the set {abcd} and we want to check whether we can turn this into {dabc}. The allowed modifications are:

  • Switch 0-th with 1-st
  • Switch 2nd with 3rd

Using these rules it is impossible to convert the starting set into the target set and thus something that comes as close as possible to it, is enough.

The exact measure of "closeness" is not relevant for me, as long as the end-result is always the same, no matter from which permutation of the set I start (provided it is possible to arrive at the solution using only the given modifications). So in this example it should not matter whether I start from {abcd} or e.g. {badc}.

The other characteristic of the searched for algorithm is that if it is possible to reach the given target set with the allowed modifications, the algorithm should always transform my start set into the target set.


The underlying application

The context to where I intend to use an algorithm as described above is to determine whether two Tensor specifications (for our intents and purposes a "Tensor" is a multidimensional array) are really referring to one and the same element, taking the Tensor's symmetry into account.

So for instance a Tensor could be $G^{ij}_{ab}$ and its symmetries allow exchange index $i$ with $j$. Therefore $G^{ji}_{ab}$ must have the exact same value because there exists a symmetry-relation that tells us that these two must be equal. $G^{ij}_{ba}$ on the other hand would be a different element.

My idea was to establish something of a "canonical" order of indices such that Tensor elements that are really the same, end up being written in the exact same way and therefore can be compared for equality by a simple == check.

In order to do that I would map the indices into a set of indices (e.g. {ijab}) which I can sort, since my indices are comparable. Therefore I can create a target set of indices that is independent of the starting set and thus I can use that as a common reference point for all Tensors that contain the same indices (but maybe in different order).


Clarification

The ultimate algorithmic goal is to solve the following problem:

Given a bunch of Tensors, say $G^{ij}_{ab}$, $G^{ji}_{ab}$ and $G^{ia}_{jb}$, the task is to recognize which of these Tensors are actually equal.

Two Tensors are equal if they have the same index-structure or there exists a symmetry-transformation such that the index-structure becomes equal. A symmetry-transformation in this case is the exchange of indices.

Therefore my idea was to map the index-structure of each Tensor into a sequence of indices. In this case that'd end up being $ijab$, $jiab$ and $ iajb$.

The symmetry of the Tensors are read in as user-input and can therefore not be assumed to show any kind of specific properties. The only restriction is that they will always consist of pairwise index exchanges (possibly multiple exchanges can only be carried out together).

For instance such a symmetry operation may be to exchange index 0 with index 1.

Applying this rule, we can see that $jiab$ can be transformed into $ijab$ and thus $G^{ji}_{ab}$ is the same as $G^{ij}_{ab}$. $G{ia}_{jb}$ on the other hand can not be transformed into this form and is therefore a different Tensor element.

In order to not have to perform this analysis every time I want to compare two Tensor elements, I thought about establishing some sort of "canonical" index structure. The idea here is that all equal Tensor elements will be transformed into the same index-structure (whatever that may be exactly) whereas different Tensor elements will result in a different index-structure.

$\endgroup$
2
  • $\begingroup$ Can you specify the algorithmic task more clearly? What is the input and what is the output? For example, I'm a bit unclear about what "not known beforehand" might mean. Why do you call these sets? They appear to be strings/sequences (order matters). $\endgroup$
    – D.W.
    Commented Jun 24, 2021 at 8:03
  • $\begingroup$ @D.W. I'll try to clarify by providing some more info in my question. I call them sets because that's the first thing that came to my mind. If the term "set" implies that order doesn't matter then this is definitely wrong. They are indeed rather sequences of indices... $\endgroup$
    – Raven
    Commented Jun 24, 2021 at 14:15

2 Answers 2

2
$\begingroup$

It appears that your problem can be formalized as follows:

Input: group elements $g_1,\dots,g_m,y \in S_n$
Question: can we write $y$ as a product of the generators? i.e., does there exist $i_1,\dots,i_k$ such that $y = g_{i_1} g_{i_2} \cdots g_{i_k}$?

(Here $S_n$ represents the symmetric group on $n$ letters.) This amounts to testing membership in the group generated by $g_1,\dots,g_m$. In particular it is membership testing in a permutation group. This can apparently be solved in polynomial time, if I am understanding the following paper correctly:

Polynomial-time algorithms for permutation groups. Merrick Furst, John Hopcroft, Eugene Luks. FOCS 1980.

I'd suggest you check out Gap and Magma to see if they have algorithms for this problem.

$\endgroup$
2
  • $\begingroup$ I assume the elements in $S_n$ are meant to be the allowed operations on the input? If so then yes some operation may indeed be written as the product of other operations. Performing membership tests seems to be a way to determine whether two sequences are the same (belong to the same group). It's not exactly what I had in mind but I guess I can build on this. Thank you! $\endgroup$
    – Raven
    Commented Jun 24, 2021 at 14:55
  • 1
    $\begingroup$ @Raven, e.g., $g_i$ corresponds to a set of swaps you're allowed to do. Any re-ordering of the "set" can be viewed as an element of $S_n$; a permutation describes which indices get reordered where. $\endgroup$
    – D.W.
    Commented Jun 24, 2021 at 17:08
1
$\begingroup$

Ignoring the algorithm here, the problem with your notion of closeness between two sets needs to be solved by defining what is this "closeness" in your eyes :

  1. Does the distance between the element's position in the set VS his position in the target set matters ? If not, then the closeness score could simply be the number of elements correctly placed, and if the "distance" matters, then another problem arises.
  2. Which one is better between a set of M correctly placed elements, but X elements placed far from their target position, and a set of M-1 elements with X+1 elements placed close to their target positions ? The way that you would compute your closeness score really matters here because you may need to balance between correctly placed elements, almost correct elements, and badly placed ones.

Without this notion clarified, it would be complicated to create an algorithm to get "as close as possible to a target set".


I thought about your problem during the night, and there's a way to solve your problem with a directed search for example. The metyric proposed below only works if there's no difference between an element "close" to his target position, and one "far" from its targets position, as explained above.

First, let's talk about the "closeness metric". Let's say that for any set $S$, which contains $N$ elements, $x_i$ is a boolean which is equal to 1 if the element is well placed (identical to its place in target set), and 0 if not. The score of a set is $C_S = \sum_{i\in [1,N]} x_i * (1 + 10^{-i})$. Each correctly placed element thus adds one to the score, and adds a little digit that can be used to compare two sets with the same number of well placed elements by saying "The one with the earliest misplaced element in the set is worse" (between two sets, the one with the highest value for this metric is considered "closer" to the target set). The only utility of this score is to ensure that between X solutions with the same number of well placed elements, the same one is always chosen.

Your operations on set can be seen as edges in a graph where each node represent a configuration of the set, and edges are links between twoconfigurations when an operation (defined in your rules) allows to transform the first one into the second one. Your relations seem reversible, but if they are not, then it's a directed graph.

To construct your graph, start by adding your initial configuration as the first node, and explore it by using any operation allowed. Each new configuration is added to the graph, linking it to its origin with the defined edge. Then, repeat the operation by choosing an un-explored node. If an exploration gives one or more node that are already explored, you can ignore them as they have "already" ben reached, and there's no need to reach them again.

The process continues until you either reach the solution (target set), or you have no more nodes to explore. Use the metric in a priority queue in order to explore nodes that are close to your target before nodes that are far from it. The best node according to your metric is always the result of the algorithm.

The search can be long if N is very big, and/or if you have many possible operations, but it guarantees that you will always find the same solution, and the target one if possible.

$\endgroup$
8
  • $\begingroup$ I think either would work. As I was trying to say: I only require the algorithm to create an exact match if possible and otherwise it needs to be consistent (arrive at the same result no matter the starting set - provided that result can even be reached from there). The "as close as possible" was basically my current best idea of how to achieve the latter. The exact metrics and exact outcome in the latter case aren't actually important to me as in the end it boils down to a binary decision: The sets are the same or they are not. $\endgroup$
    – Raven
    Commented Jun 23, 2021 at 15:32
  • $\begingroup$ Sorry for the very hand-wavy explanation but this is the best I was able to come up with xD $\endgroup$
    – Raven
    Commented Jun 23, 2021 at 15:33
  • $\begingroup$ No problem, I can understand the need to have reproductible results. You need to define a metric, but you don't really care about the result in the "impossible to reproduce the target" case. $\endgroup$
    – Nicinic
    Commented Jun 23, 2021 at 15:59
  • $\begingroup$ I edited my answer with a rough draft of an algorithm that you could use in order to solve your problem. Take a look $\endgroup$
    – Nicinic
    Commented Jun 24, 2021 at 7:07
  • $\begingroup$ @Nicinic I think this would be the trivial algorithm. It can run in up to $O(n!)$ time, at the worst case. Yes, it does increase efficiency when the number of possible configurations is small, but generally speaking this won't be the case. For $k$ operations we can expect at least $2^k$ different configurations we can end up with. So for $k=\omega(\log(n))$ this algorithm isn't even polynomial. $\endgroup$
    – nir shahar
    Commented Jun 24, 2021 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.