Find the Minimum Cost Array Permutation
Source: leetcode
Difficulty: Hard
Tags: array, dynamic-programming, bit-manipulation, bitmask

You are given an array `nums` which is a permutation of `[0, 1, 2, ..., n - 1]`. The **score** of any permutation of `[0, 1, 2, ..., n - 1]` named `perm` is defined as:


`score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|`


Return the permutation `perm` which has the **minimum** possible score. If *multiple* permutations exist with this score, return the one that is lexicographically smallest among them.


 


**Example 1:**



**Input:** nums \= \[1,0,2]


**Output:** \[0,1,2]


**Explanation:**


**![](https://assets.leetcode.com/uploads/2024/04/04/example0gif.gif)**


The lexicographically smallest permutation with minimum cost is `[0,1,2]`. The cost of this permutation is `|0 - 0| + |1 - 2| + |2 - 1| = 2`.



**Example 2:**



**Input:** nums \= \[0,2,1]


**Output:** \[0,2,1]


**Explanation:**


**![](https://assets.leetcode.com/uploads/2024/04/04/example1gif.gif)**


The lexicographically smallest permutation with minimum cost is `[0,2,1]`. The cost of this permutation is `|0 - 1| + |2 - 2| + |1 - 0| = 2`.



 


**Constraints:**


- `2 <= n == nums.length <= 14`
- `nums` is a permutation of `[0, 1, 2, ..., n - 1]`.




C++ solution:
static const int __ = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    typedef uint_fast16_t u16;

    struct DSU {
        vector<int> e;
        
        DSU(int n) : e(n, -1) {};

        int get(int v) { return e[v] < 0 ? v : e[v] = get(e[v]); }

        bool same_set(int v, int w) { return get(v) == get(w); } 

        int size(int v) { return -e[get(v)]; }

        bool unite(int v, int w) {
            v = get(v), w = get(w);
            if (v == w) return false;
            if (e[v] > e[w]) swap(v, w);
            e[v] += e[w];
            e[w] = v;
            return true;
        }
    };

    vector<int> findPermutation(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n, -1), h(n), res(n);
        for (int i = 0; i < n; ++i) h[nums[i]] = i;
        DSU dsu(n);
        u16 vis = 0;
        for (int i = 0; i < n; ++i) {
            if (vis & (1 << i)) continue;
            for (int j = i; !(vis & (1 << j)); j = nums[j]) {
                vis |= (1 << j);
                dsu.unite(j, i);
            }
        }
        auto check = [&](){
            DSU g = dsu;
            u16 need = 0;
            for (int i = 0; i < n; ++i) {
                if (ans[i] != -1) {
                    int x = nums[ans[i]];
                    if (x < i) for (int j = x; j < i; ++j) need |= (1 << j);
                    else for (int j = i; j < x; ++j) need |= (1 << j);
                }
            }
            for (int i = 0; i < n - 1; ++i)
                if ((need & (1 << i)) && !g.unite(i, i + 1)) return false;
            vector<int> dir(n - 2, -1);
            u16 cant = 0;
            auto work = [&](int x, int d) {
                dir[x] = (dir[x] >= 0 && dir[x] != d) ? 0 : d;
            };
            for (int i = 0; i < n; ++i) {
                if (ans[i] != -1) {
                    int x = nums[ans[i]];
                    if (x < i) {
                        for (int j = x; j + 1 < i; ++j) work(j, 1);
                        if (x > 0) work(x - 1, 2);
                        if (i + 1 < n) work(i - 1, 2);
                    } else if (x > i) {
                        for (int j = x - 1; j > i; --j) work(j - 1, 2);
                        if (x + 1 < n) work(x - 1, 1);
                        if (i > 0) work(i - 1, 1);
                    } else {
                        if (x + 1 < n) cant |= (1 << x);
                        if (x > 0) cant |= (1 << (x - 1));
                    }
                }
            }
            for (int i = 0; i + 2 < n; ++i)
                if (((need & (1 << i)) && (need & (1 << (i + 1))) && dir[i] == 0) ||
                    ((need & (1 << i)) && (cant & (1 << i)))) return false;
            if ((need & (1 << (n - 2))) && (cant & (1 << (n - 2)))) return false;
            for (int i = 0; i < n - 1; ++i) {
                if ((need & (1 << i)) || (cant & (1 << i)) ||
                    (dir[i - 1] == 0 && (i > 0 || i < n - 2))) continue;
                g.unite(i, i + 1);
            }
            for (int i = 0; i < n; ++i)
                if (!g.same_set(0, i)) return false;
            return true;
        };
        u16 cyc = 0;
        for (int i = 0, cnt = 0, j = 0; true; i = ans[i]) {
            res[j] = i;
            ++j;
            cyc |= (1 << i);
            ++cnt;
            ans[i] = 0;
            while ((cnt < n && (cyc & (1 << ans[i]))) || !check()) ++ans[i];
            if (!ans[i]) break;
        }
        return res;
    }
};

Go solution:
var memo [][]int
var bestPick [][]int
var nums []int

func findPermutation(numbers []int) []int {
    n := len(numbers)
    nums = numbers
    memo = make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, 1 << n)
    }
    bestPick = make([][]int, n)
    for i := range bestPick {
        bestPick[i] = make([]int, 1 << n)
    }
    getScore(0, uint16(1))

    construct := func() []int {
        ans := make([]int, n)
        for i, last, mask := 0, 0, 1; i < len(bestPick); i++ {
            ans[i] = last
            last = bestPick[last][mask]
            mask |= 1 << last
        }
        return ans
    }

    return construct()

}

func getScore(last int, mask uint16) int {
    if bits.OnesCount16(mask) == len(nums) {
        return abs(last - nums[0])
    }
    if memo[last][mask] > 0 {
        return memo[last][mask]
    }
    minScore := math.MaxInt
    for i, n := range nums {
        if (mask & (1 << i)) != 0 { continue }
        nextMinScore := abs(n - last) + getScore(i, mask | (1 << i))
        if nextMinScore < minScore {
            minScore = nextMinScore
            bestPick[last][mask] = i
        }
    }
    memo[last][mask] = minScore
    return memo[last][mask] 
}

func abs(i int) int {
    if i > 0 {
        return i
    }
    return -i
}

Java solution:
class Solution {
    static final int MISSING = -1;

    int n;
    int[] nums;
    int[][][] cache, take;

    /**
     * Returns the minimum "remaining" score <em>|last - nums[perm[i]]| + |perm[i] - nums[perm[i + 1]] + ... +
     * |perm[n - 1] - nums[first]|</em>, where <em>perm[i], perm[i + 1], ..., perm[n - 1]</em> are not in
     * {@code bitset}.
     * <p>
     * Mutates {@code take}.
     *
     * @param bitset the set of elements taken
     * @param first the first element taken
     * @param last the most recent element taken
     * @return the minimum "remaining" score
     */
    int dp(int bitset, int first, int last) {
        if (cache[bitset][first][last] != MISSING) {
            return cache[bitset][first][last];
        }

        if (bitset == (1 << n) - 1) {
            return Math.abs(last - nums[first]);
        }

        int resCost = Integer.MAX_VALUE;
        int resTake = 0;
        for (int i = 0; i < n; ++i) {
            if ((bitset & (1 << i)) == 0) {
                int potential = dp(bitset | (1 << i), first, i) + Math.abs(last - nums[i]);
                if (potential < resCost) {
                    resCost = potential;
                    resTake = i;
                }
            }
        }

        take[bitset][first][last] = resTake;
        return cache[bitset][first][last] = resCost;
    }

    public int[] findPermutation(int[] nums) {
        n = nums.length;
        this.nums = nums;

        cache = new int[1 << n][n][n];
        take = new int[1 << n][n][n];
        for (int[][] matrix : cache) {
            for (int[] row : matrix) {
                Arrays.fill(row, MISSING);
            }
        }

        int resCost = dp(1, 0, 0);
        int resTake = 0;
        for (int i = 1; i < n; ++i) {
            int potential = dp(1 << i, i, i);
            if (potential < resCost) {
                resCost = potential;
                resTake = i;
            }
        }

        int[] perm = new int[n];
        for (int i = 0, bitset = 1 << resTake, first = resTake, last; i < n; ++i) {
            perm[i] = last = resTake;

            bitset |= 1 << (resTake = take[bitset][first][last]);
        }
        return perm;
    }
}

JavaScript solution:
//#region Heap
/**
 * @template TItem
 * @typedef {Object} HeapConstructorParams<TItem>
 * @property {(a: TItem, b: TItem) => boolean} isMorePriority
 * @property {TItem[]} [initialData]
 * @property {(node: TItem, index: number) => any} [onHeapIndexChange]
 */

/**
 * @template TItem
 */
class Heap {
  /**
   * @private
   * @type {(TItem | undefined)[]}
   */
  _nodes;

  /**
   * @private
   * @type {number}
   */
  _size;

  /** @type {boolean} */
  isEnabledTrackingIndex;

  /** @param {HeapConstructorParams<TItem>} param0 */
  constructor({ initialData, isMorePriority, onHeapIndexChange }) {
    /**
     * @private
     * @param {TItem | undefined} a
     * @param {TItem | undefined} b
     * @returns {boolean}
     */
    this._isMorePriority = (a, b) => {
      if (b == undefined) return true;
      if (a == undefined) return false;
      return isMorePriority(a, b);
    };

    /**
     * @private
     */
    this._onHeapIndexChange = onHeapIndexChange;

    /**
     * @private
     * @param {number} index
     * @param {TItem} node
     */
    this._setNodeAndTriggerChange = (index, node) => {
      if (index >= this._nodes.length) return;
      this._nodes[index] = node;

      if (this.isEnabledTrackingIndex) this._onHeapIndexChange?.(node, index);
    };

    this.isEnabledTrackingIndex = !!onHeapIndexChange;
    if (initialData?.length) this.build(initialData);
    else {
      this._nodes = [];
      this._size = 0;
    }
  }

  /**
   * @param {number} index
   */
  floatNode(index) {
    let parentIndex;
    let node = this._nodes[index];

    while ((index - 1) >> 1 >= 0) {
      parentIndex = (index - 1) >> 1;
      if (this._isMorePriority(this._nodes[parentIndex], node)) break;

      this._setNodeAndTriggerChange(index, this._nodes[parentIndex]);
      index = parentIndex;
    }
    this._setNodeAndTriggerChange(index, node);
  }

  /**
   * @param {number} index
   */
  sinkNode(index) {
    let childIndex;
    let node = this._nodes[index];

    while (index * 2 + 1 < this._nodes.length) {
      childIndex = index * 2 + 1;
      if (
        childIndex + 1 < this._nodes.length &&
        this._isMorePriority(
          this._nodes[childIndex + 1],
          this._nodes[childIndex]
        )
      )
        childIndex++;

      if (this._isMorePriority(node, this._nodes[childIndex])) break;

      this._setNodeAndTriggerChange(index, this._nodes[childIndex]);
      index = childIndex;
    }
    this._setNodeAndTriggerChange(index, node);
  }

  /**
   * Sink/Float node.
   * @param {number} index
   */
  adjustNode(index) {
    this.sinkNode(index);
    this.floatNode(index);
  }

  /**
   * @param {TItem[]} data
   */
  build(data) {
    const isEnabledTrackingIndex = this.isEnabledTrackingIndex;
    this.isEnabledTrackingIndex = false;

    this._nodes = [...data];
    this._size = data.length;
    const lastNonLeafIndex = (data.length - 2) >> 1;
    for (let i = lastNonLeafIndex; i >= 0; i--) {
      this.sinkNode(i);
    }

    if (isEnabledTrackingIndex) {
      this.isEnabledTrackingIndex = true;
      this._nodes.forEach((node, index) => {
        this._onHeapIndexChange?.(node, index);
      });
    }
  }

  /**
   * @param {TItem} node
   */
  add(node) {
    this._nodes.push(node);
    this._size++;
    this.floatNode(this._nodes.length - 1);
  }

  pop() {
    if (this._nodes[0] == null) return null;

    const result = this._nodes[0];
    this._nodes[0] = null;
    this._size--;
    this.sinkNode(0);

    return result;
  }

  get size() {
    return this._size;
  }

  getTop() {
    return this._nodes[0];
  }

  getSecond() {
    return this._isMorePriority(this._nodes[1], this._nodes[2])
      ? this._nodes[1]
      : this._nodes[2];
  }

  clear() {
    this._nodes = [];
    this._size = 0;
  }
}
//#endregion

let dists = new Uint8Array(229376);
let oo = 200;

let temp = new Uint8Array(14);

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findPermutation = function (nums) {
  let n = nums.length;

  let fullMask = 1 << n;
  dists.fill(oo, 0, n * fullMask);
  --fullMask;

  /**
   * @type {Heap<{ code, dist }}
   */
  let h = new Heap({
    isMorePriority: (a, b) => {
      return a.dist < b.dist;
    },
  });

  dists[0] = 0;
  h.add({
    code: 0,
    dist: 0,
  });

  let resVal = oo;

  while (h.size) {
    let { code, dist } = h.pop();
    if (dist > resVal) break;
    if (dist > dists[code]) continue;

    let mask = code & fullMask;

    if (mask == fullMask) {
      resVal = dist;
      continue;
    }

    let node = code >> n;

    for (let newNode = 0, b = 1; newNode < n; ++newNode, b <<= 1) {
      if (mask & b) continue;

      let newMask = mask | b;
      if (!newNode && newMask != fullMask) continue;

      let newCode = (newNode << n) | newMask;
      let newDist = dist + Math.abs(newNode - nums[node]);

      if (newDist < dists[newCode]) {
        dists[newCode] = newDist;
        h.add({
          code: newCode,
          dist: newDist,
        });
      }
    }
  }

  let res = new Uint8Array(n);

  let code = fullMask;
  let mask = fullMask;

  for (let i = 1; i < n; ++i) {
    for (let pNode = 1, b = 2; pNode < n; ++pNode, b <<= 1) {
      if (!(mask & b)) continue;

      let pMask = mask ^ (1 << res[i - 1]);
      let pCode = (pNode << n) | pMask;
      if (dists[code] != dists[pCode] + Math.abs(res[i - 1] - nums[pNode]))
        continue;

      res[i] = pNode;
      mask = pMask;
      code = pCode;
      break;
    }
  }

  return res;
};

Python solution:
"""
minimum cost 2 * (num cycles in nums - 1)
"""

def components(permutation):
    ncomp = 0
    p = [*permutation]
    for i, pi in enumerate(p):
        if pi != -1:
            ncomp += 1
            while pi != -1:
                p[i] = -1
                i = pi
                pi = p[i] 
    return ncomp

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        ncomp = components(nums)
        max_cost = 2*(ncomp-1)
        pi = [0]

        def f(cost):
            if len(pi)==n:
                return cost+abs(pi[-1]-nums[0]) == max_cost 

            j = pi[-1]
            
            for i, num in enumerate(nums):
                c = abs(j-num)
                if i in pi or cost+c > max_cost:
                    continue
                pi.append(i)
                if f(cost+c):
                    return True
                pi.pop()
        
            return False
            
        f(0)

        return pi

Ruby solution:
def find_permutation(nums)
  n = nums.size

  def components(nums)
    n = nums.size
    visited = Array.new(n, false)
    count = 0
    (0...n).each do |i|
      next if visited[i]
      count += 1
      j = i
      until visited[j]
        visited[j] = true
        j = nums[j]
      end
    end
    count
  end

  ncomp = components(nums)
  target = 2 * (ncomp - 1)

  result = []
  used = Array.new(n, false)

  backtrack = lambda do |path, current_sum|
    if path.size == n
      last = path[-1]
      first = path[0]
      total = current_sum + (last - nums[first]).abs
      if total == target
        result.replace(path)
        return true
      end
      return false
    end

    if path.empty?
      return false if used[0]
      used[0] = true
      path.push(0)
      found = backtrack.call(path, current_sum)
      path.pop
      used[0] = false
      found
    else
      (0...n).each do |i|
        next if used[i]
        prev = path[-1]
        term = (prev - nums[i]).abs
        new_sum = current_sum + term
        next if new_sum > target

        used[i] = true
        path.push(i)
        found = backtrack.call(path, new_sum)
        if found
          return true
        end
        path.pop
        used[i] = false
      end
      false
    end
  end

  backtrack.call([], 0)
  result
end