How to find k evenly-distributed elements from the set of all n！ permutations over n alternatives?

Joe Zhou

12/21/22, 11:00 AM

Let $C=\{ c_1, c_2, \cdots,c_n \}$ be a set of $n$ alternatives and $T$ be the set of all strict complete orderings on $C$. For any two $t_1$ and $t2$ in $T$, their (Kendal-tau) distance $d(t_1, t_2)$ is defined as the number of pairwise disagreements between $t_1$ and $t_2$.

My Question: How to find $k$ (much smaller than $n!$) different elements from $T$ such that they are "evenly ditributed" in $T$ with respect to this (Kendal-tau) distance $d$?

For example, the k+1 elements $0, 1/k, 2/k, \cdots, (k-1)/k, 1$ are evenly distributed in the interval [0,1].

0 + 3

permutation

Hagen von Eitzen

12/21/22, 1:45 PM

$k=n$ cyclic permutations have mutual distance $n$. -- Whenever $n=a+b$ with $a,b>0$, cyclic permutations of the first $a$ and of the last $b$ elements give us $k=ab$ elements such that each has (several) nearest neighbours at distance $\min\{a,b\}$.

Joe Zhou

12/21/22, 3:19 PM

Thank you so much. So these n cyclic permutations (with mutual distance n) are evenly distributed in the set of all permutations?

Joe Zhou

12/22/22, 12:50 AM

Can we simply apply the k-medoids algorithm?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to find k evenly-distributed elements from the set of all n！ permutations over n alternatives?

TH: จะหาองค์ประกอบที่กระจายอย่างสม่ำเสมอ k จากชุดของการเรียงสับเปลี่ยนnï¼ทั้งหมดผ่านทางเลือก n ได้อย่างไร

RO: Cum să găsiți k elemente distribuite uniform din mulțimea tuturor nï¼ permutări peste n alternative?

RU: Как найти k равномерно распределенных элементов из множества всех n¼ перестановок по n альтернативам?

VI: Làm cách nào để tìm k phần tử phân bố đều từ tập hợp tất cả nï¼ hoán vị trên n phương án?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.