[Question]
  [
Find a maximally profitable sequence of exchanges given an exchange rate table.
---
As an example consider the currencies **A**riary (your home currency), **B**aht, **C**edi, and **D**enar where the rate from one to another (after any transaction rate has been levied) is given by the (row, column) entry in the exchange rate table below:
```
                       TO
       A          B          C          D
   A   0.9999     1.719828   4.509549   0.709929
F  B   0.579942   0.9999     2.619738   0.409959
R
O  C   0.219978   0.379962   0.9999     0.149985
M
   D   1.39986    2.429757   6.409359   0.9999
```
Obviously exchanging **A** for **A** is not a great idea as this desk will happily charge you for doing nothing.
Less obviously, but true with this table, exchanging **A** for any other currency and then exchanging back again is a loss maker:
```
via B: 1.719828 × 0.579942 = 0.997400489976
via C: 4.509549 × 0.219978 = 0.992001569922
via D: 0.709929 × 1.39986  = 0.99380120994
```
However, exchanging **A** to **D** then **D** to **B** then **B** back to **A** *does* profit (given enough capital not to succumb to rounding):
```
0.709929 × 2.429757 × 0.579942 = 1.0003738278192194
```
One could repeatedly take this "free lunch" while the opportunity exists.
But an even more enticing chain exists here, namely **A** to **D** then **D** to **C** then **C** to **B** and finally **B** back to **A**:
```
0.709929 × 6.409359 × 0.379962 × 0.579942 = 1.0026612752037345
```
---
### Challenge Details
Given an exchange rate table in any reasonable format which fixes the meaning of the home-currency (e.g. 1st row and 1st column are always the home-currency)  
(or given such a table and a home-currency index)  
find a\* maximal arbitrage sequence of exchanges **starting and ending with the home currency** as indexes into the currency list **without repeating the use of any exchange** (i.e. a Y->X exchange may follow an X->Y one, but an X->Y may not follow an X->Y).
If no such profitable opportunity exists yield an empty list, or some other result not confusable with an identified opportunity.  
- e.g. for the above example (**A->D,D->C,C->B,B->A**):
* using 0-indexing one might return `[[0,3],[3,2],[2,1],[1,0]]` or `[0,3,2,1,0]`
* using 1-indexing one might return `[[1,4],[4,3],[3,2],[2,1]]` or `[1,4,3,2,1]`
Other formats are fine so long as there is no ambiguity.  
- One thing to watch out for is that it is possible for the best opportunity to be a single transaction from home->home (a foolish desk). If you decide to go with excluding the home currency index from both ends of the flat option above (i.e. `[3,2,1]` or `[4,3,2]`) and an empty list for "no opportunity" then make sure the home->home is not also an empty list.
\* If multiple equally profitable valid opportunities happen to exist, return any of them, some of them, or all of them.
[The Bellman-Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) is one way to approach this, but probably not the best suited for golf.
### Test Cases
Inputs shown are in the arrangement used in the example, and the results shown use 0-indexing to list the to-currency-indices (when an opportunity exists the home currency is at the trailing end only; no opportunity is an empty list).
```
[[0.999900, 1.719828, 4.509549, 0.709929],
 [0.579942, 0.999900, 2.619738, 0.409959],
 [0.219978, 0.379962, 0.999900, 0.149985],
 [1.399860, 2.429757, 6.409359, 0.999900]]  ->  [3, 2, 1, 0]
[[0.9999, 1.5645, 0.9048, 1.0929],
 [0.6382, 0.9999, 0.5790, 0.6998],
 [1.1051, 1.7269, 0.9999, 1.2087],
 [0.9131, 1.4288, 0.8262, 0.9999]]  ->  [1, 2, 0]
[[0.9999, 1.4288, 0.8262, 0.9131],
 [0.6998, 0.9999, 0.5790, 0.6382],
 [1.2087, 1.7269, 0.9999, 1.1051],
 [1.0929, 1.5645, 0.9048, 0.9999]]  ->  [1, 2, 3, 1, 0]
[[1.002662, 1.719828, 4.509549, 0.709929],
 [0.579942, 0.999900, 2.619738, 0.409959],
 [0.219978, 0.379962, 0.999900, 0.149985],
 [1.399860, 2.429757, 6.409359, 0.999900]]  ->  [3, 2, 1, 0, 0]
[[1.002662, 1.719828, 4.509549, 0.709929],
 [0.579942, 1.002604, 2.619738, 0.409959],
 [0.219978, 0.379962, 1.003000, 0.149985],
 [1.399860, 2.429757, 6.409359, 1.002244]]  ->  [3, 3, 2, 2, 1, 1, 0, 0]
[[0.9999, 1.4288, 0.8262, 0.9131],
 [0.6998, 0.9999, 0.5790, 0.6382],
 [1.2087, 1.7269, 1.0001, 1.1051],
 [1.0929, 1.4974, 0.9048, 0.9999]]  ->  [1, 2, 2, 0]
[[0.9999, 1.3262, 0.7262, 0.9131],
 [0.6998, 0.9999, 0.5490, 0.6382],
 [1.2087, 1.7269, 0.9999, 1.2051],
 [1.0929, 1.5645, 0.9048, 0.9999]]  ->  [3, 2, 3, 1, 0]
[[0.9999, 1.5645, 0.9048, 0.5790],
 [0.6382, 0.9999, 0.5790, 0.3585],
 [1.1051, 1.7269, 0.9999, 0.6391],
 [1.7271, 2.6992, 1.5645, 0.9999]]  ->  [1, 2, 0]  and/or  [3, 2, 0]
[[0.9999, 1.2645, 0.7048, 0.3790],
 [0.4382, 0.9999, 0.3790, 0.1585],
 [1.0001, 1.5269, 1.0001, 0.4391],
 [1.5271, 2.4992, 1.3645, 0.9999]]  ->  []
[[0.9999, 1.2645, 0.7048, 0.3790],
 [0.4382, 0.9999, 0.3790, 0.1585],
 [0.9999, 1.5269, 1.4190, 0.4391],
 [1.5271, 2.4992, 1.3645, 0.9999]]  ->  [2, 2, 0]
```
---
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the shortest solution in bytes wins, but competition should be made intra-language too, so don't let code-golfing languages put you off submitting in your favourite one!
  
[Answer]
# JavaScript (ES6), ~~122~~ ~~113~~ 103 bytes
Takes input as a transposed matrix with respect to the format described in the challenge. Returns a string describing the exchanges in `(from,to)` format.
```
a=>(g=(s,x=b=0,h='')=>a.map((r,y)=>~h.search(k=`(${x},${y})`)||g(s*r[x],y,h+k),x|s<b||(b=s,p=h)))(1)&&p
```
First test case: [Try it online!](https://tio.run/##TY7RboMwDEXf9xV5qNpk81ISEoKlpT9SITVQClu7gsg0gUr36yxFQqpfbOvec@0v9@t80X22P@/X5lhOJzs5u6OVpR56m9sIarvZMLtz/Nu1lHYwhOWv5r50XVHTsz3Q1a2/w@o23NmBjWNF/Wu37zMYoH47M@hH/5GPI82th9bWjDEq2HrdTkVz9c2l5Jemoie6fyFkTyKOoSB0bRCVfExSIJoUiOAxYpqQDGar4EZgKlN4guIAJQGSXEk02ixexXWEWuFDSQSa@IlKuIow1rh4I24iRDnnBQX1PAkVbuuFIhnJGCPbbfDHITQ8FySSTf8)
More test cases: [Try it online!](https://tio.run/##rZTdTsIwFIDveYpeGG211v63J7G@CFniQGT@QpgxEKevju0GDM0Qie5mbXpOz/dtPb3PX/NyOLubvpw/T25Gy9uwzMMVHgdc0nkYBE6LcHJCwlXOnvIpxjO6iJOPgpWjfDYs8EO4xkdv83d69LZ4J9ekqsa4PJ315xld0OLsgdB5VV4OqgoPQkmnoSCEYEGOj6fL4eS5nDyO2ONkjG9xv4dQH3EG8aHxbZWXFAkmuBFpDkIJlNE6SjBjtaGbaMGctPVbS@/XUXGVa5@ijAO6tbWXVrZbcZBNQQCftpDcu3U0ylBGCLq4SJEURSCOsl5vD/mXjZoCbblE2EWejFryhNhBnoS29OIn6fxUneSKpsFO/sjJpd1UBV2PpABwtY2KVrbVcAK89NtsKialdBkVwRm3jtXMcDAa0ooV4NRWlmWagzLQOjkOq/8RV8DUI6FjbdNlpmqzpPX/Zk0a14e6pTx1qFpdTGr9Ta7xaxT3WP71/Glwesf5S3Bc/PX8/UfzqBXWz83j1vD6gOaRO@DVb5pn17WVCN3ea0sma7nn2vouuVpUpukMq@AH/Ai@/AQ)
### Commented
```
a => (                  // given the exchange rate matrix a[][]
  g = (                 // g = recursive function taking:
    s,                  //   s = current amount of money
    x = b = 0,          //   x = ID of current currency, b = best result so far
    h = ''              //   h = exchange history, as a string
  ) =>                  //  
  a.map((r, y) =>       // for each row at position y in a[]:
    ~h.search(          //   if we can't find in h ...
      k = `(${x},${y})` //     ... the exchange key k from currency x to currency y
    ) ||                //   then:
    g(                  //   do a recursive call to g() with:
      s * r[x],         //     s = new amount obtained by applying the exchange rate
      y,                //     x = y
      h + k             //     h = h + k
    ),                  //   end of recursive call
    x | s < b ||        //   if x is our home currency and s is greater than or equal to b
    (b = s, p = h)      //   then set b to s and set p to h
  )                     // end of map()
)(1)                    // initial call to g() with s = 1
&& p                    // return p
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~143~~ ~~125~~ 124 bytes
```
lambda M:g(M)[1]
g=lambda M,s=[],p=1,x=0:max([(p,s)]*-~-x+[g(M,s+[(x,y)],p*M[x][y],y)for y in range(len(M))if(x,y)not in s])
```
[Try it online!](https://tio.run/##bZFLboMwEIb3nMJLSBzLNn5NJI7ACVwvqJqkkRKCQhaw6dXp2IIg1LLxPP5/5hvRja/vRyunc/Ux3Zr751dD6uMlrwsvQnaplhLtKx9oVwk6VPx4b4bc5x3ti7A7/ByGvUcH7fc@H@hYoG5X@yH4MWB2fjzJSK4teTbt5ZTfTi0OL67nJG0fr9jqQzHVlfecAX6cUyKYFeCko0QxzUEroIQzywEkBJoRlGoLoGQsLybJjABbulhTKNWLVAoAm8olmszGxJlQAE4nqWAlxibNUhKstpSYOKvUsJpCyOoVN8Jqo3Tqc@VizldMU7r3vvgidtpqcNG8U3At0snSwCoVTHJn5ykgyiRR0qU7nFyvSDhbnnJu20WG9oUH92541MyDnDNP3Ps/jxazJB749/A3T/e8ti9yxj@9hpsYk2z6BQ "Python 2 – Try It Online")
Uses 0-based indexing (0 is the home currency); returns a list of tuples of the exchanges yielding the max payout.
The approach is brute force: via the recursion, we end up visiting every non-edge-repeating path starting at `0` (for `n` being the number of currencies, this gives a maximum *depth* of `n^2`). For the subset of these paths also ending with '0', we maximize the payoff.
[Answer]
# Haskell, 175 bytes
```
e?l|e`elem`l=0|2>1=1
w[]=[]
w l=[maximum l];0!q=[q]
n!c@(v,i,(h,l))=do{j<-[0..3];c:((n-1)!(v*l!!i!!j*(i,j)?h,j,((i,j):h,l)))}
z l=w$filter(\(v,e,_)->v>1&&e==0)$12!(1,0,([],l))
```
[Try it here](https://repl.it/repls/NanoRoastedTechnology)
]