☰

对列表进行排序并计算排序排列的符号

tag-icon • tag-icon latex3 sorting
对列表进行排序并计算排序排列的符号

我想要对 LaTeX3 clist 进行排序，同时计算排序排列的符号，也就是对(-n)^s列表s进行排序所需的交换次数。

例如，如果我以 开始，23,7,18,17,16,15,8,6,19,4,3,2那么符号为 ，+1因为我可以先交换7和19然后交换6和，对此列表进行排序7。

我认为使用 LaTeX3 可以使用类似以下方法来实现此目的：

\clist_gsort:Nn \g_test_clist
{
  \int_compare:nTF { #1 > #2 }
    { \sort_return_same: }
    {
      \int_gset:Nn \g_sign_int {\int_eval:n {\g_sign_int*-1}}
      \sort_return_swapped:
    }
}

不幸的是，尽管这种方法通常有效，但有时也会失败，尤其是上面的列表。我对以下 MWE 的解释是，LaTeX 通过执行以下交换序列对此列表进行排序：

  • 交换 7 和 17 得到23,17,18,7,16,15,8,6,19,4,3,2
  • 交换 8 和 8 得到 23,17,18,8,16,15,7,6,19,4,3,2
  • 交换 6 和 19 得到23,17,18,8,16,15,7,19,6,4,3,2
  • 交换 7 和 19 得到23,17,18,8,16,15,19,7,6,4,3,2
  • 交换 8 和 19 得到23,17,18,19,16,15,8,7,6,4,3,2
  • 交换 15 和 19 得到23,17,18,15,16,19,8,7,6,4,3,2*
  • 交换 16 和 19 得到23,17,18,15,19,16,8,7,6,4,3,2
  • 交换 17 和 19 得到23,19,18,15,17,16,8,7,6,4,3,2
  • 交换 18 和 19 得到23,18,19,15,17,16,8,7,6,4,3,2*

显然，我不明白这里发生了什么，因为最后一个序列没有排序，并且它与 LaTeX 返回的正确排序的最终序列不一致。标有星号的两个交换是有问题的，因为根据我的理解，它们不应该发生。代码还返回了错误的符号。

我有两个问题：

  1. 这到底是怎么回事
  2. 是否可以使用\clist_gsort:Nn或其他技术来计算排序排列的符号。

这是我的 MWE：

\documentclass{article}
\usepackage{expl3}
\parindent=0pt
\parskip=4mm

\begin{document}
\ExplSyntaxOn

\clist_new:N  \g_test_clist
\clist_gset:Nn \g_test_clist {23,7,18,17,16,15,8,6,19,4,3,2}

\int_new:N   \g_sign_int
\int_gset:Nn \g_sign_int {1}

Initial~list~\clist_use:Nn \g_test_clist {,}.\newline
Initial~sign:~$\int_use:N \g_sign_int$.\par

\clist_gsort:Nn \g_test_clist
{
  \int_compare:nTF { #1 > #2 }
    { \sort_return_same: }
    {
      \int_gset:Nn \g_sign_int {\int_eval:n {\g_sign_int*-1}}
      Swapping:~#1~and~#2:~new~sign$=\int_use:N \g_sign_int$.\newline
      \sort_return_swapped:
    }
}
\par
Final~list:~\clist_use:Nn \g_test_clist {,}.\newline
Final~sign:~$\int_use:N \g_sign_int$.

\ExplSyntaxOff

\end{document}

生成结果：

在此处输入图片描述

答案1

您可以从最左边的项目开始比较，然后删除它并重新开始比较，直到没有更多项目为止。

每当出现反转时，我就增加计数器；最终，我检查奇偶校验并相应地返回 1 或负 1。

\documentclass{article}

\ExplSyntaxOn

\NewDocumentCommand{\computesign}{m}
 {
  \int_zero:N \l_pi_sign_int
  \pi_sign_compute:n { #1 }
  \ensuremath { \int_if_odd:nTF { \l_pi_sign_int } { -1 } { 1 } }
 }

\clist_new:N \l__pi_sign_clist
\int_new:N \l_pi_sign_int

\cs_new_protected:Nn \pi_sign_compute:n
 {
  \clist_set:Nn \l__pi_sign_clist { #1 }
  \__pi_sign_compute:
 }

\cs_new_protected:Nn \__pi_sign_compute:
 {
  \clist_pop:NN \l__pi_sign_clist \l__pi_sign_first_tl
  \clist_if_empty:NF \l__pi_sign_clist
   {
    \clist_map_inline:Nn \l__pi_sign_clist
     {
      \int_compare:nT { \l__pi_sign_first_tl < ##1 } { \int_incr:N \l_pi_sign_int }
     }
    % restart the recursion
    \__pi_sign_compute:
   }
 }

\ExplSyntaxOff

\begin{document}

\computesign{23,7,18,17,16,15,8,6,19,4,3,2}

\computesign{23,7,18,17,16,15,8,6,19,4,2,3}

\computesign{1,2}

\computesign{2,1}

\computesign{1,2,3}

\computesign{1,2,3,4}

\computesign{1}

\computesign{}

\end{document}

在此处输入图片描述

答案2

正如 Joeseph 指出的那样，\clist_sort:Nn使用合并排序。据我所知，没有简单的方法可以使用排序所使用的比较来计算排序排列的符号，所以我需要以不同的方式执行此操作。我实际上只需要符号，而不是排序列表。下面的代码提供了一种查找符号的方法，即列表中反转的(-1)^s次数s。

\documentclass{article}
\usepackage{expl3}
\parindent=0pt
\parskip=4mm

\begin{document}
\ExplSyntaxOn

\clist_new:N  \l_test_clist
\clist_set:Nn \l_test_clist {23,7,18,17,16,15,8,6,19,4,3,2}

\int_new:N \l_i_int
\int_new:N \l_j_int
\int_new:N \l_sign_int
\cs_new:Nn \__compute_sign_of_test_clist: {
  % increment \l_sign_int for every inversion in \l_test_clist
  \int_set:Nn \l_sign_int {0}
  \int_set:Nn \l_i_int {1}
  \int_until_do:nNnn {\l_i_int} = {\clist_count:N \l_test_clist}
  {
    \int_set:Nn \l_j_int {\int_eval:n {\l_i_int} }
    \int_until_do:nNnn {\l_j_int} = {\clist_count:N \l_test_clist}
    {
      \int_incr:N \l_j_int
      \int_compare:nT { \clist_item:Nn\l_test_clist{\l_i_int} < \clist_item:Nn\l_test_clist{\l_j_int} }
      {
        \int_incr:N \l_sign_int
      }
    }
    \int_incr:N \l_i_int
  }
  \int_if_even:nTF {\l_sign_int} {+}{-}
}

List~\clist_use:Nn \l_test_clist {,}.\newline
Sign:~$\__compute_sign_of_test_clist:$

\ExplSyntaxOff

\end{document}

相关内容