☰

随机排列 LaTeX3 序列的元素

tag-icon • tag-icon expl3
随机排列 LaTeX3 序列的元素

我正在寻找一种方法来对序列变量的元素进行打乱expl3。以下初始化并输出此类序列变量的代码可以作为起点：

\documentclass{article}
\usepackage{expl3}

\ExplSyntaxOn

%initialize ordered seq
\seq_gset_from_clist:Nn\g_my_seq{0,1,2,3,4,5,6,7,8,9}
%shuffle \g_my_seq
% ? ? ?

\begin{document}
\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}
\end{document}

答案1

木制版本。没有优化。没有“专家”写过此代码。

\seq_new:N \l_alexg_origin_seq
\seq_new:N \l_alexg_destiny_seq
\int_new:N \l_alexg_random_int
\int_new:N \l_alexg_current_int
\cs_new_protected:Npn \seq_shuffle:N #1
 {
  \seq_set_eq:NN \l_alexg_origin_seq #1
  \seq_clear:N \l_alexg_destiny_seq
  \prg_replicate:nn { \seq_count:N #1 }
   {
    \int_set:Nn \l_alexg_random_int { \int_rand:nn { 1 } { \seq_count:N \l_alexg_origin_seq } }
    \int_zero:N \l_alexg_current_int
    \seq_clear:N \l_tmpa_seq
    \seq_map_inline:Nn \l_alexg_origin_seq
     {
      \int_incr:N \l_alexg_current_int
      \int_compare:nNnTF { \l_alexg_current_int } = { \l_alexg_random_int }
       { \seq_put_right:Nn \l_alexg_destiny_seq { ##1 } }
       { \seq_put_right:Nn \l_tmpa_seq { ##1 } }
     }
    \seq_set_eq:NN \l_alexg_origin_seq \l_tmpa_seq
   }
  \seq_set_eq:NN #1 \l_alexg_destiny_seq
 }

完整解释@jfbu 的回答。

\cs_new_protected:Npn \seq_shuffle_inplace:N #1
 {
  \int_zero:N \l_tmpa_int
  \seq_map_inline:Nn #1
   { 
    \int_incr:N \l_tmpa_int 
    \tl_set:cn { l_jfbu_shuffle_ \int_use:N \l_tmpa_int _tl } { ##1 } 
   }
  \int_step_inline:nnnn { \l_tmpa_int } { -1 } { 2 } 
   {
    \int_set:Nn \l_tmpb_int { \int_rand:nn { 1 } { ##1 } }
    \tl_set_eq:Nc \l_tmpa_tl { l_jfbu_shuffle_##1_tl }
    \tl_set_eq:cc { l_jfbu_shuffle_##1_tl } { l_jfbu_shuffle_ \int_use:N \l_tmpb_int _tl }
    \tl_set_eq:cN { l_jfbu_shuffle_ \int_use:N \l_tmpb_int _tl } \l_tmpa_tl
   }
 \tl_set:Nx #1 % more manual approach, ideally using \seq_set_from_clist:Nx
  {
   \s__seq
   \int_step_function:nnnN { 1 } { 1 } { \l_tmpa_int } \__jfbu_seq_construct:n
  }
 }
\cs_new:Npn \__jfbu_seq_construct:n #1
 { \exp_not:N \__seq_item:n { \exp_not:v { l_jfbu_shuffle_#1_tl } } }

答案2

我会使用 Lua。它的可读性更强。

\documentclass{article}
\usepackage{expl3}
\usepackage{luacode}

\begin{luacode*}
function shuffle(list)
   for i = #list,2,-1 do
      local j = math.random(i)
      list[i], list[j] = list[j], list[i]
   end
   tex.sprint(table.concat(list,","))
end
\end{luacode*}

\ExplSyntaxOn

\cs_generate_variant:Nn \seq_gset_from_clist:Nn { Nf }

\cs_new_protected:Npn \seq_shuffle_inplace:N #1
{
  \seq_gset_from_clist:Nf #1 { \lua_now_x:n { shuffle({ [[ \seq_use:Nn #1 { ]] , [[ } ]] }) } }
}

\seq_gset_from_clist:Nf \g_my_seq { 0,1,2,3,4,5,6,7,8,9 }

\seq_shuffle_inplace:N \g_my_seq

\begin{document}

\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}

\end{document}

答案3

我实际上只是添加了\seq_shuffle:N和\seq_gshuffle:N到expl3（开发版本：https://github.com/latex3/latex3/）。据我所知，它比这里的其他解决方案（LuaTeX 除外）快 4 倍左右。

\documentclass{article}
\usepackage{expl3}
\ExplSyntaxOn
\seq_gset_from_clist:Nn\g_my_seq{0,1,2,3,4,5,6,7,8,9}
\seq_gshuffle:N \g_my_seq
\begin{document}
\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}
\end{document}

答案4

第二次更新

面对用户 Jfbu 方法的速度挑战，我对之前代码的中间步骤进行了一些测量。结果表明，改组本身非常快，但大部分时间都花在了使用标准函数从改组后的项目重建序列变量expl3上\seq_put_left:Nn。

所以，\seq_put_left:Nn被宏替换基于递归，还利用了有关序列变量内部的知识expl3（通过应用此类变量来确定\show）。大型序列发生的输入堆栈溢出错误可以通过以下方法修复：↗这个答案，以及↗评论由用户 Manuel 提供。

代码可读性强，紧凑，纯净expl3，并且速度非常快。

完整示例：

\documentclass{article}
\usepackage{expl3}\ExplSyntaxOn

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% shuffling acc to Durstenfeld-Knuth
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\cs_new_protected:Npn\seq_shuffle:N#1{
  \int_zero_new:N\l_items_int
  %count and convert seq elements into numbered tokenlist vars
  \seq_map_inline:Nn#1{
    \int_incr:N\l_items_int
    \tl_set:cn{item_\int_use:N\l_items_int}{##1}
  }
  %shuffle seq elements
  \int_step_inline:nnnn{\l_items_int}{-1}{2}{
    \tl_set:Nx\l_j_tl{\int_rand:nn{1}{##1}}
    \tl_set_eq:Nc\l_tmpa_tl{item_##1}
    \tl_set_eq:cc{item_##1}{item_\l_j_tl} \tl_set_eq:cN{item_\l_j_tl}\l_tmpa_tl
  }
  %rebuild seq variable "the hard way" by recursion
  \tl_set:Nx#1{\s__seq\_seq_build:w 1\q_stop}
}
\cs_new:Npn\_seq_build:w #1\q_stop{
  \if_int_compare:w#1>\l_items_int
    \exp_after:wN\use_none_delimit_by_q_stop:w
  \else:
    \exp_not:N\__seq_item:n{\tl_use:c{item_#1}}
  \fi:
  \exp_after:wN\_seq_build:w\int_use:N\__int_eval:w #1+1\__int_eval_end:\q_stop
}  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\seq_new:N\g_my_seq
\sys_gset_rand_seed:n{ 123456 }

\begin{document}
\typeout{++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}
%shuffle seq with 1000 items
\int_step_inline:nnnn{0}{1}{999}{
  \seq_put_right:Nn\g_my_seq{#1}
}
\pdfresettimer \seq_shuffle:N\g_my_seq
\typeout{I~shuffled~\int_use:N\l_items_int\space~items~in~\dim_to_decimal:n{\pdfelapsedtime sp}~s.}

\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}\par

%shuffle seq with 3000 items
\seq_clear:N\g_my_seq
\int_step_inline:nnnn{0}{1}{2999}{
  \seq_put_right:Nn\g_my_seq{#1}
}
\pdfresettimer \seq_shuffle:N\g_my_seq
\typeout{I~shuffled~\int_use:N\l_items_int\space~items~in~\dim_to_decimal:n{\pdfelapsedtime sp}~s.}
\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}
\typeout{++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}
\end{document}

第一次更新

好吧，这是我expl3基于谦虚的尝试来实现“到位“改组代码（Durstenfeld-Knuth方法），修改原始序列变量。

第一个版本的代码直接对作为参数传递的序列变量的两端进行操作\seq_shuffle:N。但结果却非常慢。

新版本仍然非常紧凑，将给定的 Seq var 转换为标记列表变量，访问速度更快。现在，改组速度与用户 jfbu 的解决方案一样快。

%shuffling acc to Durstenfeld-Knuth
\cs_generate_variant:Nn\seq_pop_left:NN{Nc}
\cs_new_protected:Npn\seq_shuffle:N#1{
  \tl_set:Nx\l_seq_count_tl{\seq_count:N#1}
  \int_step_inline:nnnn{1}{1}{\l_seq_count_tl}{
    \seq_pop_left:Nc#1{item_##1}
  }
  \int_step_inline:nnnn{\l_seq_count_tl}{-1}{2}{
    \tl_set:Nx\l_j_tl{\int_rand:nn{1}{##1}}
    \tl_set:Nv\l_tmpa_tl{item_##1}
    \tl_set:cv{item_##1}{item_\l_j_tl} \tl_set:cV{item_\l_j_tl}\l_tmpa_tl
    \seq_put_left:Nv#1{item_##1}
  }
  \seq_put_left:Nv#1{item_1}
}

完整示例：

\documentclass{article}
\usepackage{expl3}\ExplSyntaxOn

%shuffling acc to Durstenfeld-Knuth
\cs_generate_variant:Nn\seq_pop_left:NN{Nc}
\cs_new_protected:Npn\seq_shuffle:N#1{
  \tl_set:Nx\l_seq_count_tl{\seq_count:N#1}
  \int_step_inline:nnnn{1}{1}{\l_seq_count_tl}{
    \seq_pop_left:Nc#1{item_##1}
  }
  \int_step_inline:nnnn{\l_seq_count_tl}{-1}{2}{
    \tl_set:Nx\l_j_tl{\int_rand:nn{1}{##1}}
    \tl_set:Nv\l_tmpa_tl{item_##1}
    \tl_set:cv{item_##1}{item_\l_j_tl} \tl_set:cV{item_\l_j_tl}\l_tmpa_tl
    \seq_put_left:Nv#1{item_##1}
  }
  \seq_put_left:Nv#1{item_1}
}

%initialize ordered seq
\seq_new:N\g_my_seq
\int_step_inline:nnnn{999}{-1}{0}{
  \seq_put_left:Nn\g_my_seq{#1}
}

%shuffle
\seq_shuffle:N\g_my_seq

\begin{document}
\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}
\end{document}

旧版本：

它看起来非常紧凑，但需要定义三个额外的标记列表变量供内部使用。另一方面，我不知道它在时间方面的效率；必须在序列的两端重复使用“弹出”和“推送”操作，以隔离随机选择的序列项。

\cs_new_protected:Npn\seq_shuffle:N#1{
  \int_step_inline:nnnn{\seq_count:N#1}{-1}{2}{
    \tl_set:Nx\l_j_tl{\int_rand:nn{1}{##1}}
    \int_step_inline:nnnn{1}{1}{\l_j_tl-1}{
      \seq_pop_left:NN#1\l_tmpa_tl \seq_put_right:NV#1\l_tmpa_tl
    }
    \seq_pop_left:NN#1\l_chosen_tl
    \int_step_inline:nnnn{1}{1}{\l_j_tl-1}{
      \seq_pop_right:NN#1\l_tmpa_tl \seq_put_left:NV#1\l_tmpa_tl
    }
    \seq_put_right:NV#1\l_chosen_tl
  }
  %transfer remaining element to the destination sequence
  \seq_pop_left:NN#1\l_chosen_tl \seq_put_right:NV#1\l_chosen_tl
}

完整示例：

\documentclass{article}
\usepackage{expl3}\ExplSyntaxOn

\cs_new_protected:Npn\seq_shuffle:N#1{
  \int_step_inline:nnnn{\seq_count:N#1}{-1}{2}{
    \tl_set:Nx\l_j_tl{\int_rand:nn{1}{##1}}
    \int_step_inline:nnnn{1}{1}{\l_j_tl-1}{
      \seq_pop_left:NN#1\l_tmpa_tl \seq_put_right:NV#1\l_tmpa_tl
    }
    \seq_pop_left:NN#1\l_chosen_tl
    \int_step_inline:nnnn{1}{1}{\l_j_tl-1}{
      \seq_pop_right:NN#1\l_tmpa_tl \seq_put_left:NV#1\l_tmpa_tl
    }
    \seq_put_right:NV#1\l_chosen_tl
  }
  \seq_pop_left:NN#1\l_chosen_tl \seq_put_right:NV#1\l_chosen_tl
}

%initialize ordered seq
\seq_gset_from_clist:Nn\g_my_seq{0,1,2,3,4,5,6,7,8,9}
\seq_shuffle:N\g_my_seq

\begin{document}
\seq_use:Nnnn\g_my_seq{~and~}{,~}{,~and~}
\end{document}

相关内容