1) The necessary approach:
A faster implementation would be to sort the values ββof the data frame and align the columns, respectively, based on the resulting indices after np.argsort .
pd.DataFrame(df.columns[np.argsort(df.values)], df.index, np.unique(df.values))

Using np.argsort gives us the data we are looking for:
df.columns[np.argsort(df.values)] Out[156]: Index([['a1', 'a2', 'a3', 'a4'], ['a3', 'a1', 'a2', 'a4'], ['a4', 'a2', 'a3', 'a1']], dtype='object')
2) Slow generalized approach:
A more generalized approach, although at the cost of some speed / efficiency, would be to use apply after creating a dict display of the rows / values ββpresent in the data frame, with their corresponding column names.
Use the dataframe constructor later after converting the resulting rows to their list view.
pd.DataFrame(df.apply(lambda s: dict(zip(pd.Series(s), pd.Series(s).index)), 1).tolist())
3) Faster generalized approach:
After receiving the list of dictionaries from df.to_dict + orient='records' we need to change the corresponding key and value pairs, iterate through them in a loop.
pd.DataFrame([{val:key for key, val in d.items()} for d in df.to_dict('r')])
Test Case Example:
df = df.assign(a5=['Foo', 'Bar', 'Baz'])
Both of these approaches produce:

@piRSquared EDIT 1
generalized solution
def nic(df): v = df.values n, m = v.shape u, inv = np.unique(v, return_inverse=1) i = df.index.values c = df.columns.values r = np.empty((n, len(u)), dtype=c.dtype) r[i.repeat(m), inv] = np.tile(c, n) return pd.DataFrame(r, i, u)
1 I would like to thank user @ piRSquared for coming up with a very fast and generalized alternative based on numpy SOLN.sub>